알고리즘 - 미로 출구찾기(재귀)

int[][] 로 정의된 미로에서 특정 출발점에서 탈출 경로가 있는지 확인하는 메서드이다.

 

고려해야할 사항은 해당 경로의 방문여부와 해당 경로의 이웃한 칸들의 탈출 경로 유무이다. (재귀를 통해서 확인)

재귀는 탈출(종료) 조건을 지정해주는것이 중요하다는것을 다시한번 알 수 있는 코드였다.

 

public class MazeCase {
    public static void main(String[] args) {
        System.out.println(findPath(0, 0));
    }
    // 탈출할 수 있는 경로가 있으므로 true 리턴.

    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},
    };
    // 0(갈수있는길), 1(벽), 2(방문해봤지만 경로 없는곳), 3(가본곳인데 아직 경로 있는지 확인은 안된곳)
    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 findPath(int x, int y) {
        // 적합하지 않은 인덱스면 false 리턴
        if (x < 0 || y < 0 || x >= N || y >= N) return false;

        // 도착한 곳이 길이 아닐경우(벽이거나 이미 방문한곳) false 리턴
        else if (maze[x][y] != PATHWAY_COLOUR) return false; // 갈수있는 길이 아니면 false 리턴

        // 도착한 곳이 출구이면 true 리턴
        else if (x == N - 1 && y == N - 1) {
            maze[x][y] = PATH_COLOUR;
            return true;
        }

        // 도착한 곳에서 갈수있는 다른 길이 있을경우 각 지점에서 다시 재귀호출
        else {
            maze[x][y] = PATH_COLOUR; // 방문했지만 아직 경로확인이 다 안되었으므로 값을 3으로 변경
            if (findPath(x - 1, y) || findPath(x, y + 1) || findPath(x + 1, y) || findPath(x, y - 1)) {
                return true; // 상,하,좌,우 중에 나갈 수 있는 경로 있으면 true리턴
            }
            maze[x][y] = BLOCKED_COLOUR; // 나가는 길이 없었을 경우 해당 경로는 못가는 경로, 2로 변경하고 false 리턴
            return false;
        }
    }
}