[JAVA] Recursion 응용: 미로찾기

이번 포스팅에서는 미로가 주어졌을 때 재귀(Recursion)를 통해 경로를 찾는 방법에 대해 알아보겠습니다.

Recursive Thinking

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

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

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

---

 

출구까지 길이 있으냐(yes) 없느냐(no)

위의 1번과 2번을 모두 적용해서 답을 찾아야 합니다. 이동할 위치의 셀이 통로에 속한 셀이면서 2번을 적용할 수 있을 때 Recursion 실행합니다.

 

KEY. 이 Recursion이 무한루프에 빠지지는 않는지 확인해야 합니다! 때문에 Base case가 반드시 필요합니다.

이 문제 같은 경우는 한 칸 이동을 한 다음에 다시 자신이 왔던 것으로 돌아가며 무한 루프에 빠질 위험이 존재합니다.

1. 방문한 위치 표시(mark)

2. 일단 Recursion을 호출하고 앞에서 조건문으로 예외 처리. Recursion의 호출 횟수는 증가

---

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;     // white
    private static final int WALL_COLOUR = 1;       // blue
    private static final int BLOCKED_COLOUR = 2;    // red
    private static final int PATH_COLOUR = 3;       // green

    public static void printMaze(int[][] maze){
        for(int i=0; i<maze.length; i++){
            for(int j=0; j<maze[i].length; j++){
                System.out.print(maze[i][j]+" ");
            }
            System.out.println("\n");
        }
        System.out.println("\n");
    }
    
    public static boolean findMazePath(int x, int y){
        if(x<0 || y<0 || x>=N || y>N)   // 유효한 범위 검증. N*N 그리드이기 떄문에 0부터 N-1까지 가능
            return false;
        else if(maze[x][y] != PATHWAY_COLOUR )  // visited(방문 or 길이 없거나) or 벽일 때
            return false;
        else if(x==N-1&&y==N-1){ // 출구에 도착했을 때
            maze[x][y] = PATH_COLOUR;   // 방문한 위치를 녹색으로 칠함
            return true;
        }
        else{
            maze[x][y] = PATH_COLOUR;   // 일단 지나온 길은 GREEN
            if(findMazePath(x-1, y)||findMazePath(x, y-1)||findMazePath(x+1, y)||findMazePath(x, y+1)) // 각 방향별로 한 번씩 진행
                return true;
        }
        maze[x][y] = BLOCKED_COLOUR;
        return false;   // 이전 위치로 돌아가 다른 방향에서 탐색
    }

    public static void main(String[] argrs){
        printMaze();
        findMazePath(0,0);
        printMaze();
    }
}