Recursion 응용(1)

미로찾기

순환적인 방식으로 생각해보기

- 현재 위치에서 출구까지 가는 경로가 있기 위해서는 밑의 두 가지 조건 중 하나가 만족해야 한다.

1) 현재 위치가 출구여야 한다.

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

- 순환 형식을 이용하여 프로그래밍할 경우에는 무한루프에 빠질 수 있는 경우를 주의해야 한다.

- 슈도 코드

boolean findPath (x, y)

if (x, y) is the exit

return true;

else

for each neighboring cell (x', y') of (x, y) do

if (x', y') is on the pathway

if findPath(x', y')

return true;

return false;

-> 이 경우 무한루프에 빠질 수 있는 위험성을 내포하고 있다.

-> 인접한 셀이라는 조건에 의해 이미 방문했던 셀을 반복해서 재방문하며 무한루프에 빠질 가능성이 있다.

- 슈도 코드 보완 1

boolean findPath (x, y)

if (x, y) is the exit

return true;

else

mark (x, y) as a visited cell;

for each neighboring cell (x', y') of (x, y) do

if (x', y') is on the pathway and not visited

if findPath(x', y')

return true;

return false;

-> 이미 방문했던 셀을 표시함으로서 재방문의 위험성을 제거해낼 수 있게 된다.

- 슈도 코드 보완 2

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 neighboring cell (x', y') of (x, y) do

if findPath (x', y')

return true;

return false;

-> 보완 1과 거의 같으나 따로 방문했던 셀이 있으면 false를 반환하게 하는 조건을 걸었다는 차이가 있다.

-> 이 방식은 보완 1에 비해 순환함수 출력 횟수는 더 많아지나 코드는 더 간결해진다는 차이가 있다.

- 구현

public class MazeProblem {
    private static int N = 8;
    //1은 벽이며 0은 길임
    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 } };
    //path는 방문했으며 아직 출구로 가는 경로가 될 가능성이 있는 셀
    //blocked는 방문했으며 출구로 가는 경로가 아님이 밝혀진 셀
    private static final int PATHWAY_COLOR = 0; // white
    private static final int WALL_COLOR = 1; // black
    private static final int BLOCKED_COLOR = 2; // red
    private static final int PATH_COLOR = 3; // green
    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_COLOR)
            return false;
        else if (x == N - 1 && y == N - 1) {
            maze[x][y] = PATH_COLOR;
            return true;
        } else {
            maze[x][y] = PATH_COLOR;
            if (findMazePath(x - 1, y) || findMazePath(x, y + 1) 
                    || findMazePath(x + 1, y) || findMazePath(x, y - 1))
                return true;
            maze[x][y] = BLOCKED_COLOR; // dead end
            return false;
        }
    }
    private static void printMaze() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                System.out.print(j == N - 1 ? maze[i][j] : (maze[i][j] + "\t"));
            System.out.println();
        }
    }
    public static void main(String[] args) {
        findMazePath(0, 0);
        printMaze();
    }
}