미로찾기 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]]

위는 미로를 표현한 2차원 리스트이다. 1은 벽이라 통과할 수 없고 0은 통로이다. 출발점은 [0][0]이고 출구는 [n-1][n-1]인 지점이다.

순환적 사고

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

1) 현재 위치가 출구이거나 혹은

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

def findpath(x,y):

if maze[x][y] == exit: return True #현 위치가 출구라면 True 리턴

else:#현위치인 maze[x][y]를 기준으로 사방에 하나라도 통로가 있다면 True 리턴

if findpath(x)(y) or maze(x)(y+1) or maze(x+1)(y) or maze(x-1)(y-1):return True

#아니면 나아갈 수 있는 통로가 하나도 없으므로 False 리턴 

return False 

무한 루프에 빠지지 않는지 고려해야 한다. 위 코드는 maze[x][y]와 maze[x-1][y]간에 왔다갔다 하면서 함수 호출이 무한 반복될수도 있다.

이미 지나간 곳과 지나가지 않은 곳을 구별해야 한다.

지나갈 수 있는 곳과 출구 변수에 즉, 통로에 특정 값을 넣어 구별한다. maze[x][y] = path

통로를 지나면서 지나갈 수 있는 길인지, 방문하지 않았는지 확인한 다음 함수를 호출하는 것이 아닌

[x][y] 주변을 인자로 넘겨 함수를 호출한 뒤 함수의 처음 부분에 벽이거나 방문했다면 False를 리턴한다.

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]
]
pathway=0
wall=1
blocked=2
path=3

def Path(x,y):
    n=len(Maze)
    if x<0 or y<0 or x>=n or y>=n or Maze[x][y]!=pathway:
        return False
    elif x==n-1 and y==n-1:
        Maze[x][y]=path
        return True
    else:
        Maze[x][y]=path
        if Path(x,y+1) or Path(x+1,y) or Path(x,y-1) or Path(x-1,y):
            return True
        Maze[x][y]=blocked
        return False
Path(0,0)
for i in Maze:
    print(i)

결과는 아래와 같다. 3은 미로를 탈출을 위한 경로다. 1번은 벽, 2번은 방문했으나 더 이상 지나갈 수 없는 경로다.

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

 [3, 1, 3, 3, 3, 1, 0, 1], 

 [3, 3, 3, 1, 3, 3, 3, 1], 

 [0, 1, 1, 1, 0, 1, 3, 3]]