Recursion의 응용: 미로찾기

1. Recursive Thinking

1) 현재 위치가 출구이거나 혹은

2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

3) Pseudo-code는 다음과 같이 나타낼 수 있다. 

boolean findPath(x,y)

if (x, y) is the exit // 처음 위치가 출구일 경우

return true;  

else

mark (x, y) as a visited cell;

for each neighbouring cell (x', y') of (x, y) do

if (x', y') is on the pathway and not visited // (x', y')가 길이고, 방문하지 않았을 경우

if findPath(x', y') // recursive

return true;

return false;  

 
public class Maze {
	private static int N=8;
	private static int[][] maze = {
		{0,0,0,0,0,0,0,1},
		{0,1,1,0,1,1,0,1},
		{0,0,0,1,0,0,0,1},
		{0,1,0,0,1,1,0,0},
		{0,1,1,1,0,0,1,1},
		{0,1,0,0,0,1,0,1},
		{0,0,0,1,0,0,0,1},
		{0,1,1,1,0,1,0,0}
	};
	
	private static final int PATHWAY_COLOR = 0; //white, visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell
	private static final int WALL_COLOR = 1; 	//blue
	private static final int BLOCKED_COLOR = 2;	//red, visited이며 출구까지의 경로상에 있지 않음이 밝혀진 cell
	private static final int PATH_COLOR = 3;	//green
	
	public static boolean findMazePath(int x, int y){
		if(x<0 || y<0 || x>=N || y>=N)
			return false;
		else if(maze[x][y] != PATHWAY_COLOR)
			return false;
		else if(x==N-1 && y==N-1){
			maze[x][y] = PATH_COLOR;
			return true;
		}
		else{
			maze[x][y] = PATH_COLOR;
			if(findMazePath(x-1,y) || findMazePath(x,y+1)
					|| findMazePath(x+1, y) || findMazePath(x, y-1)){
				return true;
			}
			maze[x][y] = BLOCKED_COLOR;
			return false;
		}
	}
	
	public static void main(String[] args) {
		findMazePath(0, 0);
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				System.out.print(maze[i][j]);
			}
			System.out.println();
		}
		
	}
}

/*
<결과>
31121121
32212221
31221122
31112211
31333121
33313331
01110133
*/