9x9 미로에서 입구 (1, 1) 에서 출구 (7, 7) 까지 가는 길을 찾는다. 같은 미로를 파일 세 개로 나눠 풀었다.
방향은 셋 다 같은 방식으로 다룬다.
di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]
for k in range(4):
ti, tj = i + di[k], j + dj[k]
바깥 테두리가 전부 벽인 2 라서 범위를 벗어나는지 따로 확인하지 않아도 된다. 벽 검사 하나가 경계 검사까지 겸한다.
재귀
def finding(enter):
i, j = enter
maze[i][j] = 1
if (i, j) == exit:
for row in maze:
print(row)
print()
for k in range(4):
ti, tj = i + di[k], j + dj[k]
if maze[ti][tj] == 0:
finding((ti, tj))
maze[i][j] = 0
들어가면서 1 로 막고 나오면서 0 으로 되돌린다. 되돌리기 때문에 이미 지나온 칸이 다른 경로에서 다시 쓰일 수 있다.
그래서 이 코드는 경로 하나가 아니라 모든 경로를 찾는다. 출구에 닿아도 멈추지 않고 미로를 찍은 뒤 계속 돈다. 이 미로에서는 7개가 나온다.
스택
stack = []
stack.append((i, j, 0))
i, j, d = stack.pop()
def finding(i, j):
maze[i][j] = 1
...
for k in range(4):
ti, tj = i + di[k], j + dj[k]
if maze[ti][tj] == 0:
stack.append(((ti, tj, k)))
finding(ti, tj)
maze[i][j] = 0
재귀를 스택으로 바꿔보려고 만든 파일인데 결과적으로는 재귀 그대로다. stack.append 를 해놓고 그걸 꺼내 쓰는 반복문이 없다. 함수 안에서 여전히 자기 자신을 부른다.
위쪽의 pop 도 함수 밖에서 한 번 실행되고 끝이라 시작점을 꺼내는 것 말고는 하는 일이 없다.
돌려보면 재귀 버전과 출력이 완전히 같다. 스택은 붙어만 있고 흐름을 바꾸지 않는다.
재귀를 진짜로 스택으로 옮기려면 while stack: 으로 돌면서 꺼내고, 그 안에서 되돌릴 시점을 직접 관리해야 한다. 함수 호출이 알아서 해주던 걸 손으로 해야 하는 부분이 그것이다.
큐
queue = []
queue.append((i, j, [(i, j)]))
while len(queue) != 0:
i, j, path = queue.pop(0)
if (i, j) == exit:
print(path)
for k in range(4):
ti, tj = i + di[k], j + dj[k]
if maze[ti][tj] == 0 and (ti, tj) not in path:
queue.append((ti, tj, path+[(i, j)]))
이쪽은 구조가 다르다. 미로를 고치지 않고 경로를 통째로 큐에 담아 다닌다.
미로에 방문 표시를 하지 않는 이유가 있다. BFS는 여러 갈래가 동시에 퍼지므로 미로 한 장에 표시하면 서로의 발자국을 밟는다. 갈래마다 자기 경로를 들고 있어야 한다.
(ti, tj) not in path 로 자기가 지나온 곳만 피한다. 다른 갈래가 지난 곳은 상관없다. 그래서 이것도 모든 경로를 찾는다. 역시 7개가 나온다.
큐 버전의 어긋난 두 곳
출력을 보면 이렇다.
[(1, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), ... (7, 5), (7, 6)]
맨 앞에 (1, 1) 이 두 번 있고, 끝이 (7, 6) 이라 출구 (7, 7) 이 빠져 있다.
queue.append((ti, tj, path + [(i, j)])) 에서 붙이는 게 다음 칸 (ti, tj) 가 아니라 지금 칸 (i, j) 다. 그래서 경로에 담기는 건 항상 한 칸 뒤처진 목록이 된다.
시작할 때만 [(i, j)] 로 자기 자신을 넣고 시작하므로 첫 칸이 두 번 들어간다. path + [(ti, tj)] 로 바꾸고 시작을 [(i, j)] 그대로 두면 맞는다.
경로의 길이와 형태는 맞고 앞뒤로 한 칸씩 어긋난 것이라, 개수만 보고 넘어가면 안 보인다.