[알고리즘] Recursion의 응용 - 미로찾기

Recursion의 응용 - 미로찾기

미로찾기 문제에 대해서 생각해보도록 하자

그리드의 크기를 NxN이라고 가정한다면

[0,0]이 입구, [n-1,n-1]이 출구가 된다.

여기서 흰색으로 표시된것이 통로, 파란색은 벽 임을 가정 했을 때,

탈출 할 수있는 경로를 찾는것이 과제이다.

위의 문제를 풀수 있는 방법은 많지만 가장 간명하게 풀수있는 것이 재귀이다.

이 문제를 재귀적으로 푼다면 다음과같은 재귀적 사고가 필요하다.

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

1) 내가 있는 위치가 출구일 때(이미 내가 출구에 도달해 있을 때)

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

위의 둘중 하나를 만족해야한다.

boolean findPath(x,y)
    // 현재 위치가 출구일 떄
    if(x,y) is the exit
        return true;
    // 현재 위치가 출구가 아닐 때
    else
        for each neighouring cell (x`,y`) of (x,y) do                                                       
            if(x`,y`) is on the pathway
                if findPath(x`,y`)
                    return true;
        return false;
 

우선 간단하게 생각하기 위해 decision problem버전으로 먼저 생각해본다

 decision problem은 답이 yes거나 no 인 문제를 나타낸다.

여기서는 출구까지 가는 경로가 있으냐 없느냐를 뜻한다.

위의 코드는 decision problem의 슈도(의사) 코드이다.

findPath라는 함수가 하는 일을

x,y로 부터 출구까지 가는 경로가 있는지 없는지를 판단해서

있으면  true, 없으면  false를 리턴하는 함수이다.

우선 현재 위치가 출구 일때를 검사하고

그렇지 않을경우 4개의 인접한 '통로'인 셀 각각에 대해

출구까지 있는 경로가 있는지 재귀적으로 검사해서 true라면 자신도 true가 된다.

맨 마지막줄에 false에 주목해보자. 

for문을 빠져나와서 false까지 왔다는 것은 

4개의 셀 각각에 대해서 경로를 검사했지만 true가 없었거나 벽이었다는 것을 나타낸다. 

boolean findPath(x,y)
    // 현재 위치가 출구일 떄
    if(x,y) is the exit
        return true;
    // 현재 위치가 출구가 아닐 때
    else
        mark (x, y) as a visited cell; // 이미 방문된 위치라는 것을 표시함
        for each neighouring 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;
 

슈도 코드를 실제로 작성하기 앞서 우리는 무한 루프에 빠지지 않는가 검사해야한다.

1) base case가 있어야하며

2) base case에 수렴 해야한다.

이 옵션에 대해 검색을 진행한다면 위의 코드는 무한 루프에 빠질 가능성이있다.

만약 x, y에서 x` , y`로 함수를 호출한다면 x`,y` 입장에서 보면

초기에 호출한 x, y는 다시 x`, y`의 인접한 셀이된다.

그래서 지나 왔던 길로 다시 돌아오는 경우를 구분해야한다.

따라서 첫번째 코드를 위의 두번째 코드로 수정해야한다.

이렇게 되면 재귀 함수가 한번 호출 될 때 마다 하나의 셀이 표시가 될것이며

셀의 개수는 유한하기 때문에 무한루프에 빠지지 않는다

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 neighouring cell (x`,y`) of (x,y) do
                if findPath(x`,y`)
                    return true;
        return false;
 

다른 방법으로 위와 같이 구현할 수 있다.

두번째 예제와의 큰 차이는 없다. 취향의 차이이다.

2번째 예제보다 재귀 함수의 호출이 많아지지만 코드가 간결 해진다는 장점이 있다.

우리는 이 코드를 기반으로 코드를 작성하도록 하겠다.

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;                                                             
    private static final int WALL_COLOUR = 1;
    private static final int BLOCKED_COLOUR = 2;
    private static final int PATH_COLOUR = 3;
 
}
 

슈도코드를 자바코드로 구현했다.

우선 미로는 입력을 받지않고 2차원의 배열로 고정해두었다.

미로에서 통로는 0, 벽은 1의 값을 값도록 받는다.

추가로 이미 방문한 위치와, 그렇지 않은 위치를 표시하기위해 4가지 값들을 정의했다.

pathway - 사람이 지나다닐수 있는 통로

wall - 사람이 지나다닐수 없는 벽

blocked - 이미 방문했으나 경로가 없음

path -  이미 방문했고, 출구까지 경로가 있을지 없을지 판정이 되지않음

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_COLOUR)
        return false;
    else if(x==N-1 && y==N-1){
        maze[x][y] = PATH_COLOUR;
        return true;
    }
    else{
        maze[x][y] = PATH_COLOUR;
        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[] args){
    pringMaze();
    findMazePath(0,0);
    pringMaze();
}
 

 

다음은 초기 설정에 이어서 경로가 있는지 검사하는 함수이다.

처음에는 main에서 [0][0]으로 이 함수를 호출한다.

첫번째, 슈도코드에 없는 예외적 경우를 추가했다.

재귀로 호출할 때 좌표가 음수가 되는 경우등을 체크하지 않고 호출하므로

맨 위에 그리드의 범위내에서 동작하고있는지를 먼저 체크하도록 하는 코드를 추가했다

 

두번째로 pathway_colour가 아닌 경우는 방문했거나 벽이므로

검사없이 바로 리턴을 해주게 된다.

세번째로 x가 N-1이거나 y가 N-1일때

그 위치는 출구이므로 true를 반환하면 된다.

네번째는 위의 3개 조건을 제외한 나머지인데

우선 이 조건에 들어오면 먼저 방문했지만 출구로가는 경로인지 알수없는

path 경로 표시를 해주고

조건문을 통해 동서남북 4개의 셀을 방문하게 된다.

그중에 하나라도 경로를 찾으면 true를 반환하며 리턴을 하게되고

그렇지 않으면 미로에 blocked_colour로 표시를 해주고 false를 리턴한다.

위의 그림은 실제로 코드가 동작하는 순서를 나타냈다.

어느쪽으로 셀을 검사하느냐에 따라 그림이 달라지는데

북동남서의 순서로 셀을 시도한다는 가정하에서 그려졌다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘