PostsSeriesLabsAlgo

그래프 탐색

격자 BFS

소문은 어떻게 퍼질까

왼쪽 위에서 소문이 시작됩니다. 칸을 눌러 벽을 놓고, 한 걸음씩 퍼뜨려 보세요.

칸을 눌러 벽을 놓고, 한 걸음씩 퍼뜨려 보세요

0걸음에 닿을 수 있는 칸을 다 돌았습니다. 한 걸음마다 이웃 칸이 한 겹씩 물들었습니다.

겹이 하나씩 넓어지니 먼저 물든 칸이 더 가까운 칸입니다. 어느 칸에 처음 닿은 걸음 수가 곧 최단 거리입니다.

이렇게 가까운 곳부터 한 겹씩 넓혀 가는 방법 = BFS

BFS 의 최단 거리는 걸음 수가 같을 때만 맞다

  • 한 겹 = 한 걸음 — 겹이 넓어지는 순서가 곧 가까운 순서다
  • 처음 닿았을 때가 최단 — 나중에 다시 닿는 길은 반드시 더 멀다
  • 깨지는 경우 — 길마다 걸리는 시간이 다르면 안 맞는다. 그때는 다익스트라다

큐가 겹을 만든다

다음을 눌러 한 줄씩 넘기며 큐에 쌓이는 순서를 보세요. 아래 숫자가 그 칸까지의 걸음 수입니다.

큐← 꺼낸다
  1. 0
넣는다 →

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

큐 = 1

bfs.py
  1. 1from collections import deque
  2. 2
  3. 3def bfs(grid, start, goal):
  4. 4 q = deque([start])
  5. 5 dist = {start: 0}
  6. 6 while q:
  7. 7 r, c = q.popleft()
  8. 8 if (r, c) == goal:
  9. 9 return dist[(r, c)]
  10. 10 for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
  11. 11 nr, nc = r + dr, c + dc
  12. 12 if grid[nr][nc] == 0 and (nr, nc) not in dist:
  13. 13 dist[(nr, nc)] = dist[(r, c)] + 1
  14. 14 q.append((nr, nc))
  15. 15 return -1
0 / 31
  • popleft — 큐 맨 앞에서 꺼낸다. 먼저 넣은 칸이 먼저 나온다
  • not in dist — 이미 다녀간 칸은 다시 넣지 않는다. 이 줄이 없으면 영원히 돈다
  • dist[(r,c)] + 1 — 이웃은 나보다 딱 한 걸음 멀다

큐(deque) 대신 스택을 쓰면 어떻게 될까요?

격자 BFS 에서 틀리는 자리

  • 넣을 때 표시하지 않으면 — 같은 칸이 큐에 여러 번 들어가 느려지고 거리도 틀린다
  • list.pop(0) — 파이썬 리스트는 맨 앞을 꺼낼 때마다 전부 당긴다. deque 를 쓴다
  • 격자 밖 — 범위 검사를 빼먹으면 반대쪽 줄로 넘어간다

위 플레이어에서 도착까지 7걸음입니다. 벽을 돌아가는 길이라 직선 거리보다 깁니다.

BFS 를 꺼내라는 세 가지 신호

최단 거리를 묻는다한 칸 이동이 전부 똑같다격자나 그래프다

다음 장에서는 길마다 걸리는 시간이 다를 때 쓰는 다익스트라를 봅니다.