[알고리즘]Recursion 응용(미로찾기)

미로찾기

그림과 같이 wall 과 pathway로 구성된 미로를 탈출하는 코드를 recursion으로 구현할 수 있다.

recursive하게 생각을 해야한다.
현재 위치에서 출구까지 가는 경로가 있으려면

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

간단하게 생각해보면 다음과 같이 구현할 수 있다.

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 a pathway cell
                if findPath(x',y')
                    return true
        return false;

(x,y)에서 출구까지 경로가 있으면 true, 없으면 false를 return하는 함수이다.
(x,y)에 이웃한 셀들을 반복문으로 돌아가며 셀이 wall이 아닌 pathway이라면, 재귀적으로 그 위치에서 경로가 있는지 findPath함수를 호출한다.
하지만 여기에는 문제점이 있다. 바로 무한루프에 빠질 수 도 있다는 것이다. 만약 findPath(x',y')에서 다시 원래 위치인 (x,y)로 이동한다면 무한루프에 빠질 것이다. 이와같이 재귀함수를 사용 할 때는 무한루프빠지기 쉬으므로 주의해야 한다.

이를 해결하기 위해 다음과 같이 생각해 볼 수 있다.

• 현재위치가 출구이거나.
• 이웃한 셀들 중 하나에서 이미 가본 곳을 다시 지나지 않고 출구까지 가는 경로가 있거나.

이를 코드로 구현하면 다음과 같다

boolean findPath(x,y)
    if (x,y) is wall or (x,y) is a visited Cell
        return false;
    else if (x,y) is the exit
        return true;
    else
        mark (x,y) as visited cell;
        for each neighbouring cell (x',y') of (x,y) do
            if findPath(x',y')
                return true;
        return false

함수 제일 처음에 (x,y)가 벽이거나 이미 방문한 셀이면 false를 리턴하도록 코드를 추가하였고,
반복문을 돌며 이웃한 셀을 이동할 때 현재 위치 (x,y)를 visited cell로 표시를 하고 지나가도록 하였다.

전체코드를 구현하면 다음과 같다.

N=8
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]
]
pathwayColor=0
wallColor=1
blockedColor=2
pathColor=3

def findMazePath(x,y):
    if x<0 or y<0 or x>=N or y>=N or maze[x][y]!=pathwayColor:
        return False
    elif x==N-1 and y==N-1:
        maze[x][y]=pathColor
        return True
    else:
        maze[x][y]=pathColor
        if findMazePath(x-1,y) or findMazePath(x,y+1) or findMazePath(x+1,y) or findMazePath(x,y-1):
            return True
    maze[x][y]=blockedColor
    return False

for i in maze:
    print(i)

print(findMazePath(0,0))

for i in maze:
    print(i)

[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]
True
[3, 2, 2, 2, 2, 2, 2, 1]
[3, 1, 1, 2, 1, 1, 2, 1]
[3, 2, 2, 1, 2, 2, 2, 1]
[3, 1, 2, 2, 1, 1, 2, 2]
[3, 1, 1, 1, 2, 2, 1, 1]
[3, 1, 3, 3, 3, 1, 2, 1]
[3, 3, 3, 1, 3, 3, 3, 1]
[0, 1, 1, 1, 0, 1, 3, 3]

[3, 2, 2, 2, 2, 2, 2, 1]
[3, 1, 1, 2, 1, 1, 2, 1]
[3, 2, 2, 1, 2, 2, 2, 1]
[3, 1, 2, 2, 1, 1, 2, 2]
[3, 1, 1, 1, 2, 2, 1, 1]
[3, 1, 3, 3, 3, 1, 2, 1]
[3, 3, 3, 1, 3, 3, 3, 1]
[0, 1, 1, 1, 0, 1, 3, 3]
3번으로 표시된 부분이 경로이다.