Java - 미로 찾기

1. 문제 (미로 찾기)

• 파란색은 벽, 흰 색은 이동할 수 있는 통로를 의미
• 입구는 (0, 0), 출구는 (N-1, N-1)이며, 입구에서 시작해서 출구로 빠져나올 수 있도록 경로를 찾는다.

---

2. 생각(Recursion Thinking)

 본 문제를 Recursion(재귀)를 이용하여 풀기 위해서 Recursion 하게 생각하였다. Recursion Thinking을 하면 현재 상황을 다음과 같이 나누어서 생각할 수 있다.

 

If 현재 위치에서 출구까지 갈 수 있는 경로가 존재하려면

• 현재 위치가 출구 이거나
• 이웃한 셀들(= 현재 위치에서의 동서남북 셀)중에서 현재 위치를 지나지 않고, 출구까지 가는 경로가 있어야 한다.

 

2.1.  Write the code by recursion.

Recursion Thinking을 이용하여 코드를 작성하면 다음과 같이 작성할 수 있다.

 boolean findPath(x, y) {
	// ** 확인 1. 현재 셀(x, y)이 출구에 위치해 있는가?
	if(x, y) is the exit.
          return true;
    else 
    // ** 확인 2. 현재 셀에 이웃한 최대 4개의 셀에 대해서 확인
    	for each neighbouring cell (x', y') of (x, y) do
           if findPath(x', y')
              return true;
        return false;
}

 하지만, 위 코드에서 문제점이 발생하였는데, 바로 Recursion case가 base case에 수렴하지 않아 무한루프에 빠지게 된 것이다. 즉, 다시 말해 (x, y)에서 이웃한 셀인 (x', y')으로 이동한 다음, 다시 또 (x', y')에서 지나온 (x, y)로 이동하는 것이다. 

이로 인해 두 셀만 서로 왔다갔다하여 무한 루프에 빠지게 되는 것이다. 이를 해결하기 위해 "지나온 셀은 무시하고, 나머지 이웃한 셀에 대해서만 Recursion을 실행한다."는 조건이 필요하다. 

 

방법 1) 

boolean findPath(x, y)
    // ** 1. 현재 셀이 출구인지 
    if (x, y) is the exit
    	return true;
    else
    	// ** 2. 현재 셀에 이웃한 셀들에 대해서 재귀
        // * 2.1. 현재의 셀(x, y)을 마킹한다.
        mark (x, y) as a visited cell;
        for each neighbouring cell (x', y') of (x, y) do
            // * 2.2. 이웃한 셀(x', y')이 지나온 셀인지 확인
            if(x', y') is on the pathway and not visited
            	if findPath(x', y')
                	 return true;
        return false;

방법 2)

boolean findPath(x, y)
    // 1. 현재 셀이 벽이거나 지나온 셀인지
    if (x, y) is on the wall or a visited cell.
    	return false;
    // 2. 현재 셀이 출구인지
    else if (x, y) is the exit
    	return true;
    // 3. 이웃한 셀(x', y')에 대해서 재귀 실행
    else
    	mark (x, y) as a visited cell.
        for each neighbouring cell (x', y') of (x, y) do
        	if findPath(x', y')
            	return true;            
       	return false;

---

3. 풀이 및 코드 분석

import java.util.Scanner;

public class FindMazePath {
	// *** Initialization
	private static final int PATHWAY_COLOR = 0; // white
	private static final int WALL_COLOR = 1; // blue
	private static final int ENTRANCE_COLOR = 2; // yellow
	private static final int EXIT_COLOR = 3; // yellow
	private static final int BLOCKED_COLOR = 4; // red
	private static final int PATH_COLOR = 5; // green
	private static Scanner scan = new Scanner(System.in);
	private static int[][] maze;
	private static int size;
	
	public static void main(String[] args) {
		size = 0;	
		
		// *** Get the size of maze.
		while(true) {
			System.out.print("Enter size of maze: ");
			size = scan.nextInt();
			
			if(size<=0)
				System.out.println("The size is less than zero.");
			else
				break;
		}
		
		// *** Maze initialization.
		maze = new int[size][size];
		
		// *** Get maze information.
		for(int j=0; j<size; j++) {
			System.out.print("Enter element: ");
			for(int i=0; i<size; i++) {
				maze[j][i] = scan.nextInt();
			}		
		}
		
		// *** Get entrance & exit.
		int[] entrance = getCoordinate("entrance");
		int[] exit = getCoordinate("exit");
		maze[entrance[0]][entrance[1]] = ENTRANCE_COLOR;
		maze[exit[0]][exit[1]] = EXIT_COLOR;
		
		// *** Print the maze.
		printMaze(maze);
		// *** Find a path way of maze.
		if(findPath(entrance[0], entrance[1], exit))
			printMaze(maze);
		else 
			System.out.println("\n There is no exit to escape the maze.");
	}
	
	// ** Print maze array.
	private static void printMaze(int[][] maze) {
		System.out.println("\nMaze Array: ");
		for(int j=0; j<maze.length; j++) {
			for(int i=0; i<maze[0].length; i++) {
				if(maze[j][i]==PATHWAY_COLOR)
					System.out.print(" □");
				else if(maze[j][i]==WALL_COLOR)
					System.out.print(" ■");
				else if(maze[j][i]==ENTRANCE_COLOR)
					System.out.print(" ☆");
				else if(maze[j][i]==EXIT_COLOR)
					System.out.print(" ★");
				else if(maze[j][i]==PATH_COLOR)
					System.out.print(" v");
				else 
					System.out.print(" X");
			}
			System.out.println();
		}
	}
	
	// ** Get coordinate.
	private static int[] getCoordinate(String contents) {
		int[] coordinate = new int[2];
		
		while(true) {
			System.out.printf("Enter %s: ", contents);
			for(int i=0; i<2; i++)
				coordinate[i] = scan.nextInt();
			
			if(coordinate[0]<0 || coordinate[0]>=size || coordinate[1]<0 || coordinate[1]>=size)
				System.out.printf("The %f is out of maze.\n", contents);
			else if(maze[coordinate[0]][coordinate[1]]==1)
				System.out.print("The point is the wall.\n");
			else 
				break;
		}
		
		return coordinate;
	}
	
	// ** Find the path for exit.
	private static boolean findPath(int x, int y, int[] exit) {
		if(x<0 || x>=size || y<0 || y>=size)
			return false;
		else if(maze[x][y]!=PATHWAY_COLOR && maze[x][y]!=ENTRANCE_COLOR && maze[x][y]!=EXIT_COLOR)
			return false;
		else if(x==exit[0] && y==exit[1]) {
			maze[x][y] = PATH_COLOR;
			return true;
		}else {
			maze[x][y] = PATH_COLOR;
			if(findPath(x, y+1, exit) || findPath(x+1, y, exit) 
					|| findPath(x, y-1, exit) || findPath(x-1, y, exit))
				return true;
		}
		
		maze[x][y] = BLOCKED_COLOR;
		return false;
	}
}

---

4. 메모

• 첫 번째 방법은 Recursion을 하기 전에 해당 셀이 이미 지나올 셀인지를 확인하지만, 두 번째 방법은 해당 셀이 지나온 셀인지 확인할 필요 없이 무조건 Recursion하기 때문에 첫 번째 방법이 두 번째 방법보다 시간적으로나 효율적으로나 더 좋다고 할 수 있다.