장기판 馬 원하는 지점까지 최소움직임을 보이는 이동경로 구하기 (DP)

알고리즘2012. 3. 11. 23:17

장기판 馬 원하는 지점까지 최소움직임을 보이는 이동경로 구하기 (DP)

장기판에서 馬 가 시작지점에서 원하는 지점까지

최소 움직임을 보이는 경로를 찾는 문제이다.

이는 최소비용을 구한다는 점과 , 그 경로를 구한다는 점에서

DP( Dynamic Programming) 문제임을 눈치챌 수 있다.

이를 해결하기 위한 아이디어를

밑에 그림으로 설명을 하였다.

실제로 이 아이디어를 C언어 코드로 구현을 하였다

밑에 링크에서 코드를 볼수 있다.

http://ideone.com/QYOfU

#include <stdio.h>
#include <stdlib.h>

#define SIZE 9
int board[SIZE][SIZE];
int INF  = 0x7FFFFFFF;

int w[8][2] = {
	{1,2},{1,-2},{-1,2},{-1,-2},
	{2,1},{2,-1},{-2,1},{-2,-1}
};

int isInRange(int x, int y){
	if((0 <= x && x < SIZE)&&(0 <= y && y < SIZE)){
		return 1;
	}else{
		return 0;
	}
}

void update(int cx, int cy, int tx, int ty){
	if(board[tx][ty] != INF && board[cx][cy] > board[tx][ty] + 1){
		board[cx][cy] = board[tx][ty] + 1;
	}
}

void print_board(){
	int i,j;
	printf("------- print board -------\n");
	for(i=0; i < SIZE; i++){
		for(j=0; j < SIZE; j++){
			if(board[i][j] == INF){
				printf("INF, ");
			}else{
				printf ("%3d, ", board[i][j]);
			}
		}
		printf("\n");
	}
	printf("------- ----- ----- -------\n");
}

void print_route(int X, int Y){

printf(" ---- route -----\n");

int i,j;
	int len = 1;
	int route[SIZE][SIZE];

for(i=0; i < SIZE; i++){
		for(j=0; j <SIZE; j++){
			route[i][j] = 0;
		}
	}

route[X][Y] = len;

while(1){
		int minX, minY;
		int min = INF;
		for(i=0; i < 8; i++){
			if(isInRange(X+w[i][0], Y+w[i][1])){
				if(min > board[X+w[i][0]][Y+w[i][1]]){
					minX = X + w[i][0];
					minY = Y + w[i][1];
					min = board[X+w[i][0]][Y+w[i][1]];
				}
			}
		}
		// increse path walk length
		len++;
		X = minX;
		Y = minY;
		route[X][Y] = len;

if(min == 0){
			break;
		}
	}/*while*/

for(i=0; i < SIZE; i++){
		for(j=0; j <SIZE; j++){
			
			if(route[i][j] == 0){
				printf("   , ");
			}else{
				printf("%3d, ", route[i][j]);
			}
		}
		printf("\n");
	}

}

int getScore(int startX, int startY, int endX, int endY){
	int i,j,k;

if(!isInRange(startX, startY)){
		printf("out of range!\n");
		exit(1);	
	}
	if(!isInRange(endX, endY)){
		printf("out of range!\n");
		exit(1);	
	}

// initialize board
	for(i=0; i < SIZE; i++){
		for(j=0; j < SIZE; j++){
			board[i][j] = INF;
		}
	}
	// record minimum cost
	board[endX][endY] = 0;

print_board();

while(1){

int i,j;
		for(i=0; i < SIZE; i++){
			for(j=0; j < SIZE; j++){
				for(k=0; k < 8; k++){
					if(isInRange(i+w[k][0], j+w[k][1])){
						update(i,j,i+w[k][0], j+w[k][1]);
					}
				}
			}
		}

print_board();

if(board[startX][startY] != INF){
			printf("----- find !! -----\n");
			print_route(startX, startY);
			break;
		}

}/*while*/

return board[startX][startY];
}

int main(int argc, const char *argv[])
{

int startX=1, startY=1;
	int endX=7, endY=5;

getScore(
		startY,startX,
		endY,endX
		);
	
	return 0;
}

실제로 2차원 배열에 기록을 하면서

시작지점의 값이 INF 에서 다른 값으로 변하는 순간

바로 그값이 최소비용이다. 그리고 메모라이즈 된 값들을

이용하여 값을 역추적.. 루트를 찾아낼수 있는 것이다.

저작자표시

'알고리즘' 카테고리의 다른 글

장기판 馬 원하는 지점까지 최소움직임을 보이는 이동경로 구하기 (DP) (1)	2012.03.11
[python] 하향식 연산자 우선순위 (0)	2011.08.07
피어슨(pearson) 스코어 (1)	2011.05.09
유클라디안 스코어 (0)	2011.05.09
Fuzzy C-Means , (4)	2011.03.27
헝가리안 알고리즘 hungarian algorithm 구현 (2)	2011.02.20

Posted by 멍충한아싸

Trackback 0 Comment 1

댓글을 달아 주세요

꼬마붕어

완전상미분방정식 검색했다가 좋은 글들 보고갑니다. ^^ 이제 막 컴퓨터공학과 2학년인 사람으로써 정말 멀게만 느껴지지만 열심히 하면 성대아싸님 처럼 멋지게 프로그램도 짜보고싶습니다. ㅎㅎ!! 내일도 화이팅이요!!!

2012.03.14 00:30 신고 [ ADDR : EDIT/ DEL : REPLY ]

«이전 1 2 3 4 5 6 7 ··· 240 다음»

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

성대아싸의 멍충한 프로그래밍