Recursion의 응용 - 미로찾기

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

1. 현재 위치가 출구이거나

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

 

미로찾기(Decision problem)

public 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 on the path way
                    if findPath(x', y');
                        return true;
                return false;
    }

위 코드의 경우 (x, y)와 (x', y')가 서로 왔다갔다 하면서 무한루프에 빠질 수 있다.

public 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 path way and not visited
                    if findPath(x', y');
                        return true;
                return false;
    }

public 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 a visited cell;
            for each neighbouring cell(x', y') of (x, y) do
                if findPath(x', y');
                    return true;
                return false;
    }

public class Main {
    private static int N = 8; // 미로 크기 NxN
    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; // 길
    private static final int WALL_COLOR = 1;    // 벽 
    private static final int BLOCKED_COLOR = 2; // 방문했지만 길이 아닌경우
    private static final int PATH_COLOR = 3;    // 방문했던 길
    
    static int[][] path = { // 이동할 좌표
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
    };
    
    public static void main(String[] args) {
        print();
        boolean result = findMazePath(0, 0);
        System.out.println(result);
        print();
    }
    
    public static void print() { // 미로를 표시해 주는 함수
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }
    
    public static boolean findMazePath(int x, int y) {
        if(x < 0 || y < 0 || x >= N || y >= N) { // x, y 값이 미로를 벗어난 경우
            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;
            for(int i = 0; i < 4; i ++) {
                int nx = 0;
                int ny = 0;
                nx = x + path[i][0];
                ny = y + path[i][1];
                if(findMazePath(nx, ny)) {
                    return true;
                }
            }
            maze[x][y] = BLOCKED_COLOR; // x, y 좌표에서 길이 없는 경우 표시
            return false;
        }
    }
}

결과를 보면 길을 잘 찾은것을 볼 수있다.