PostsSeriesLabsAlgo

그래프 탐색

DFS

막다른 길까지 가 보기

왼쪽 위 시작 칸에서 오른쪽 아래 도착 칸까지 미로를 걸어 보세요. 옆 칸을 눌러 한 칸씩 갑니다. 막다른 길에서는 되돌아가기를 눌러 지나온 길로 돌아옵니다.

미로를 걸어 도착 칸에 닿으세요. 먼저 한 가지만 골라 주세요.

★ 갈림길에서 오른쪽 길로 끝까지 가면 어떻게 될까요?

★ 는 길이 둘로 갈라지는 칸이에요.

걸음 0 · 되돌아가기 0번 · 지금 길 0걸음

갈림길에서 한 길을 골라 막다른 길이나 도착이 나올 때까지 끝까지 가 보고, 막히면 돌아와 다음 길로 가는 방법 = 깊이 우선 탐색(DFS, Depth-First Search)

  • 오른쪽 길 — 위로 돌아서 9걸음에 도착한다
  • 아래 길 — 곧장 7걸음에 도착한다
  • 돌아올 길을 기억하는 곳 — 나중에 넣은 것이 먼저 나오는 더미, 스택이다. 함수가 자기를 부르는 재귀도 같은 일을 한다

같은 미로에서 가까운 칸부터 퍼지는 BFS 는 7걸음 최단을 찾습니다. 한 길을 끝까지 가는 DFS 는 오른쪽 길로 가서 9걸음에 닿습니다.

지나온 칸에 표시하지 않으면 같은 곳을 맴돈다

  • 이미 온 칸은 못 들어간다 — 미로에서 눌러 보면 막히던 규칙이다
  • 표시가 없으면 — 같은 칸을 몇 번이고 다시 넣는다. 아래 코드의 dist 가 그 표시다
  • 그래서 — 표시를 뺀 코드는 이 미로에서 1,000번을 꺼내도 도착 칸에 닿지 못했다

스택이 되돌아올 길을 기억한다

스택 = 나중에 넣은 게 먼저 나오는 더미. 위에서 걸은 것과 같은 미로입니다. 격자 BFS 코드에서 popleft() 를 pop() 으로 바꾼 코드입니다.

다음을 눌러 한 줄씩 넘기며 스택 맨 위(오른쪽 끝)가 먼저 나오는 걸 보세요. 숫자는 그 칸까지의 걸음 수입니다.

스택바닥
  1. 0
맨 위 ↔ 넣고 꺼낸다

다음을 눌러 한 줄씩 넘겨 보세요

스택 = 1

dfs.py
  1. 1def dfs(grid, start, goal):
  2. 2 rows, cols = len(grid), len(grid[0])
  3. 3 stack = [start]
  4. 4 dist = {start: 0}
  5. 5 while stack:
  6. 6 r, c = stack.pop()
  7. 7 if (r, c) == goal:
  8. 8 return dist[(r, c)]
  9. 9 for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
  10. 10 nr, nc = r + dr, c + dc
  11. 11 if not (0 <= nr < rows and 0 <= nc < cols):
  12. 12 continue
  13. 13 if grid[nr][nc] == 0 and (nr, nc) not in dist:
  14. 14 dist[(nr, nc)] = dist[(r, c)] + 1
  15. 15 stack.append((nr, nc))
  16. 16 return -1
0 / 31
  • pop() — 스택 맨 위, 가장 나중에 넣은 칸을 꺼낸다. 막다른 길이면 그 아래 칸이 맨 위가 되어 되돌아온 것이다
  • stack.append — 이웃을 쌓는다. 마지막에 쌓은 칸이 가장 먼저 나온다
  • not in dist — 이미 넣은 칸은 다시 쌓지 않는다

이 미로에서는 아래 줄 끝의 막다른 칸까지 파고든 뒤에야 도착 칸이 나옵니다. 꺼낸 횟수는 15번입니다.

아래 길의 한 칸을 벽으로 막으면, 같은 코드가 도착까지 낸 걸음 수는 몇 걸음일까요?

DFS 에서 틀리는 자리

  • 방문 표시를 빼면 — 이미 온 칸을 계속 다시 쌓아 끝나지 않는다. 위 미로에서 1,000번을 꺼내도 도착하지 못했다
  • 재귀로 쓰면 — 길이 길수록 깊이가 칸 수만큼 는다. 파이썬 기본 한도는 1000이라 벽 없는 32×32 격자(1,024칸)에서 RecursionError 가 난다. 31×31 은 된다
  • 최단 거리를 보장하지 않는다 — 같은 미로에서 BFS 는 7걸음, 이 코드는 9걸음이다
  • 이웃 쌓는 순서 — 순서를 거꾸로 바꾸면 같은 미로에서 9걸음이 7걸음으로 바뀐다. 길이 둘이면 먼저 가는 쪽이 결과를 정한다

그래서 최단 거리가 필요하면 BFS 를, 길을 끝까지 다 살펴야 하면 DFS 를 씁니다.

DFS 를 꺼내라는 세 가지 신호

모든 경로를 찾는다도달할 수 있는가한 덩어리로 이어진 곳을 찾는다

다음 장에서는 이어진 덩어리가 몇 개인지 세는 연결 요소를 봅니다.