큐와 BFS: 가까운 곳부터

매장 안내 화면에 지도가 있다. 칸으로 나눈 바닥 지도에서 입구부터 원하는 매대까지 몇 칸을 걸어야 하는지 보여 주고 싶다. 벽과 진열대는 지나갈 수 없다. 비슷한 문제가 여러 곳에 있다. 조직도나 카테고리 트리를 깊이별로 한 줄씩 그리는 일, 친구 관계에서 "2촌까지만" 추천하는 일도 그렇다. 셋 다 출발점에서 가까운 것부터 차례로 보는 문제다.

가까운 것부터 보려면 "다음에 볼 것"을 줄 세워 두는 자료 구조가 필요하다. 이 장에서는 그 줄인 큐(queue)와, 큐로 그래프(graph)를 한 겹씩 넓혀 가는 너비 우선 탐색(breadth-first search, BFS)을 본다. 개념 정리는 큐, BFS, 그래프 노트에 있다.

큐: 먼저 넣은 것을 먼저

큐는 뒤에 넣고 앞에서 꺼내는 줄이다. 먼저 넣은 것이 먼저 나오는 이 규칙을 FIFO(first-in, first-out)라 한다. 은행 번호표와 같다.

JavaScript 배열로 큐를 만들면 push로 넣고 shift로 꺼내고 싶어진다. 그런데 shift는 맨 앞 원소를 빼면서 남은 원소를 모두 한 칸씩 왼쪽으로 옮긴다(MDN: Array.prototype.shift). 원소가 n개면 꺼낼 때마다 n번 가까이 옮기니, n개를 모두 꺼내면 옮기는 횟수가 n²에 비례할 수 있다. Python 리스트의 pop(0)도 같은 이유로 O(n)이다. Python 문서는 리스트의 pop(0)과 insert(0, v)에 O(n) 메모리 이동 비용이 든다고 적고, 양 끝에서 넣고 빼는 일은 collections.deque가 양쪽 모두 거의 O(1)로 해 준다고 안내한다(Python 문서: deque).

1const queue = ['a', 'b', 'c']2let head = 03const first = queue[head] // 'a'4head++ // 배열은 그대로 두고 다음에 꺼낼 위치만 옮긴다5queue.push('d') // 뒤에 넣기

JavaScript 배열 메서드만으로는 앞에서 O(1)로 꺼낼 수 없어서, 이 책은 배열을 지우지 않고 다음에 꺼낼 위치 head만 하나씩 옮기는 방법을 쓴다. 꺼낸 칸이 메모리에 남지만 꺼내기는 O(1)이다.

격자 BFS: 거리를 한 겹씩

격자(grid)의 칸 하나를 노드(node), 상하좌우로 붙은 두 칸 사이를 간선(edge)으로 보면 격자는 그래프다(그래프 용어는 『개발 수학』 Unit 10). BFS는 이렇게 돈다.

1. 출발 칸의 거리를 0으로 적고 큐에 넣는다.
2. 큐 앞에서 칸 하나를 꺼낸다.
3. 그 칸의 이웃 중 지도 안이고, 벽이 아니고, 아직 거리가 없는 칸에 (꺼낸 칸의 거리 + 1)을 적고 큐 뒤에 넣는다.
4. 큐가 빌 때까지(또는 도착 칸을 꺼낼 때까지) 2~3을 되풀이한다.

1const grid = ['S.#', '..E']2const rows = grid.length, cols = grid[0].length3const dist = Array.from({ length: rows }, () => Array(cols).fill(-1))4dist[0][0] = 05const queue = [[0, 0]]6let head = 07while (head < queue.length) {8  const [r, c] = queue[head]9  head++10  if (grid[r][c] === 'E') break11  for (const [dr, dc] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {12    const nr = r + dr, nc = c + dc13    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue14    if (grid[nr][nc] === '#' || dist[nr][nc] !== -1) continue15    dist[nr][nc] = dist[r][c] + 116    queue.push([nr, nc])17  }18}19console.log(`거리 ${dist[rows - 1][cols - 1]}`)

거리 3

dist는 거리 기록과 방문 표시를 함께 한다. 거리를 적는 순간이 큐에 넣는 순간이라서, 같은 칸이 큐에 두 번 들어가지 않는다. 칸이 V개, 간선이 E개면(V는 vertex, E는 edge의 머리글자) 칸마다 한 번 꺼내고 간선마다 한 번 살펴보니 시간은 O(V + E)다. 격자에서는 칸마다 이웃이 넷이라 칸 수에 비례한다.

왜 처음 적은 거리가 가장 짧을까

큐 안을 들여다보면 거리 d인 칸들이 앞에, d + 1인 칸들이 뒤에 있다. 거리 d인 칸을 꺼내 이웃에 d + 1을 적어 뒤에 붙이니, 큐에는 언제나 많아야 두 종류의 거리만 있고 작은 쪽이 앞이다. 그래서 칸은 거리 0인 것 전부, 1인 것 전부, 2인 것 전부… 순서로 꺼내진다. 2절의 S.# / ..E 지도에서 큐에 들어간 칸의 거리는 차례로 0, 1, 1, 2, 3이다. 큐 안의 거리는 절대 줄지 않는다. 어떤 칸에 거리를 적는 순간은 큐에서 꺼낸 칸의 거리 + 1을 적는 순간이고, 그 뒤에 꺼내는 칸은 모두 거리가 같거나 더 크다. 그러니 어떤 칸을 처음 적을 때의 거리보다 작은 거리를 나중에 줄 방법이 없다. 처음 적은 값이 최단 거리다.

이 논리는 모든 간선의 비용이 같을 때만 성립한다. 칸마다 지나는 시간이 다르다면(계단은 3초, 복도는 1초) "먼저 꺼낸 칸 = 가까운 칸"이 깨진다. 그때는 다익스트라(Dijkstra) 알고리즘처럼 비용이 가장 작은 것을 먼저 꺼내는 우선순위 큐(priority queue)를 쓴다. 우선순위 큐는 8장(힙)에서 다룬다.

정리하면 틀린 줄은 셋이다. fill로 모든 행이 한 배열을 가리키고(행마다 새 배열을 만든다), pop()으로 뒤에서 꺼내 스택이 되고(앞에서 꺼낸다), 이미 거리가 적힌 칸을 거르지 않아 끝나지 않는다(dist가 -1인 칸만 넣는다).

단계별로 묶기: 트리 레벨 순회

카테고리 트리를 깊이별로 한 줄씩 그리려면 "이번 깊이의 노드가 어디까지인가"를 알아야 한다. 큐에서 꺼내는 순서는 이미 깊이 순서다. 남은 것은 경계다. 한 단계를 시작할 때 큐에 남은 개수를 세어 두고 정확히 그만큼만 꺼내면, 그동안 뒤에 붙인 자식들은 다음 단계 몫으로 남는다.

1const children: Record<string, string[]> = { '전체': ['의류', '가전'], '의류': ['상의', '하의'], '가전': ['TV'], '상의': ['셔츠'] }2const queue = ['전체']3let head = 04let depth = 05while (head < queue.length) {6  const count = queue.length - head7  const level: string[] = []8  for (let i = 0; i < count; i++) {9    const node = queue[head]10    head++11    level.push(node)12    queue.push(...(children[node] ?? []))13  }14  console.log(`${depth}단계: ${level.join(', ')}`)15  depth++16}

0단계: 전체
1단계: 의류, 가전
2단계: 상의, 하의, TV
3단계: 셔츠

트리는 한 노드에 이르는 길이 하나뿐이라 방문 표시가 없어도 된다. 친구 관계처럼 순환(사이클, cycle)이 있는 그래프라면 격자의 dist처럼 이미 본 노드를 기록하는 Set이 필요하다. "2촌까지 추천"은 이 레벨 순회를 2단계에서 멈추는 것이다.

F...
#..F  → 2

F.#
##.
#..  → -1