[알고리즘][Recursion] 미로찾기(Maze)

1. 미로찾기(Maze)

• 입구는 (0,0)에서 시작하여 (7,7)에 도착하면 탈출을 성공합니다.
• pathway는 통로로써 지나갈 수 있습니다.
• wall은 벽으로써 지나갈 수 없습니다.

 

Recursive Thinking

---

현재 위치에서 출구까지 가는 경로가 있으려면

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

2) 이웃한 셀들 중에서 하나에서 출구까지 가는 경로가 있어야함

 

boolean findPath(x,y)
	if (x,y) is the exit
		return true;
	else
		for each neighbouring cell (x', y') of (x,y) do
			if (x', y') is a pathway cell
				if findPath(x',y')
					return true;
		return false;

위 재귀적 사고는 무한루프에 빠질 위험성이 있습니다. 왜냐하면 이미 방문한 지역을 다시 방문하여 경로 탐색을 하기 때문입니다.

---

현재 위치에서 이미 가본 곳을 다시 지나지 않고 출구까지 가는 경로가 있으려면

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

2) 이웃한 셀들 중 하나에서 이미 가본 곳을 다시 지나지 않고 출구까지 가는 경로가 있어야함

boolean findPath(x,y)
	if (x,y) is the exit
		return true;
	else
		mark (x,y) as visited;
		for each neighbouring cell (x',y') of (x,y) do
			if (x', y') is a pathway cell and not visited
				if findPath(x',y')
					return true;
		return false;

위와 같이 이웃한 셀(x',y')들이 통로이고 아직 방문한적이 없다면 경로 탐색이 가능합니다. 그리고 (x,y) 셀에 대한 검사가 아직 없기 때문에 아래와 같이 변경할 수 있습니다.

boolean findPath(x,y)
	if (x,y) is either on the wall(벽) or a visited cell(이미 방무한 지역)
		return false;
	else if (x,y) is the exit(출구)
		return true;
	else
		mark (x,y) as visited;
		for each neighbouring cell (x',y') of (x,y) do
			if findPath(x',y')
				return true;
		return false;

 

2. 미로찾기(Maze) 구현

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_COLOUR = 0; // 일반 길
	private static final int WALL_COLOUR = 1;	 // 벽
	private static final int BLOCKED_COLOUR = 2; // 갈 수 없는 길
	private static final int PATH_COLOUR = 3;	 // 갈 수 있는 길
	
	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_COLOUR) // 일반 길을 제외한 길인 경우
		{
			return false;
		}
		else if(x==N-1 && y==N-1) // 출구인경우
		{
			maze[x][y] = PATH_COLOUR;
			return true;
		}
		else 
		{
			maze[x][y] = PATH_COLOUR;
			// 경로 상 하 좌 우 탐색
			if(findMazePath(x-1, y) || findMazePath(x+1, y) || findMazePath(x, y-1) || findMazePath(x, y+1))
			{
				return true;
			}
			maze[x][y] = BLOCKED_COLOUR; //상 하 좌 우 탐색 실패 시 해당 좌표는 벽
			return false;
		}
	}
	public static void printMaze()
	{
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<N;j++)
			{
				System.out.print(maze[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		printMaze();
		boolean answer = findMazePath(0, 0);
		printMaze();
		
		System.out.println(answer);
	}

}

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 

3 0 0 0 0 0 0 1 
3 1 1 0 1 1 0 1 
3 0 0 1 0 0 0 1 
3 1 0 0 1 1 0 0 
3 1 1 1 2 2 1 1 
3 1 3 3 3 1 2 1 
3 3 3 1 3 3 3 1 
2 1 1 1 2 1 3 3 

true

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm/tree/master/section02_Recursion_04
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌