BFS — 알고리즘 · 오승의 기술블로그

시작점에서 가까운 칸부터 한 레벨씩 넓혀 가며 둘러봅니다. 칸에 처음 닿은 순서가 곧 가장 짧은 거리라서, 최소 시간이나 최단 거리를 구할 때 씁니다.

언제 쓰나

격자나 그래프에서 가장 짧은 거리, 또는 무언가가 퍼지는 데 걸리는 최소 시간을 구할 때 씁니다.

“최소 몇 분”, “최소 몇 번 만에”, “가장 가까운”을 묻고, 한 칸 옮겨 가는 비용이 모두 같습니다.
불, 전염, 썩는 귤처럼 무언가가 이웃으로 번지고, 번지기 시작하는 곳이 처음부터 여러 곳일 수 있습니다.
이어진 칸을 모두 둘러봐야 하는 점은 DFS 플러드 필과 같지만, “몇 번째에 닿았는가”까지 알아야 합니다.

어떻게 동작하나

1분마다 한 칸씩 번진다

LeetCode 994는 격자의 칸마다 0(빈 칸), 1(싱싱한 귤), 2(썩은 귤)가 적혀 있을 때, 1분마다 썩은 귤의 상하좌우에 있는 싱싱한 귤이 썩는다면 모든 귤이 썩기까지 최소 몇 분이 걸리는지 묻는 문제입니다. 끝까지 썩지 않는 귤이 있으면 -1을 돌려줍니다.

예제 1의 격자 [[2, 1, 1], [1, 1, 0], [0, 1, 1]]을 손으로 따라가 보면 이렇습니다. 칸은 (행, 열)로 부릅니다.

처음(0분)에는 왼쪽 위 (0, 0)만 썩어 있습니다.
1분 뒤, (0, 0)의 아래 (1, 0)과 오른쪽 (0, 1)이 썩습니다.
2분 뒤, 그 둘의 이웃인 (1, 1)과 (0, 2)가 썩습니다.
3분 뒤에는 (1, 1)의 아래 (2, 1)이, 4분 뒤에는 그 오른쪽 (2, 2)가 썩습니다. 싱싱한 귤이 더 없으니 답은 4입니다.

아래 그림은 칸마다 몇 분에 썩는지를 오른쪽 위 배지로 적고, 화살표로 어느 귤이 어느 귤을 썩게 했는지 이은 것입니다. 가장 늦게 썩는 (2, 2)가 청록색입니다.

배지의 숫자는 처음 썩은 (0, 0)에서 상하좌우로 몇 칸을 건너야 그 칸에 닿는지와 같습니다. 1분에 한 칸씩 번지기 때문입니다. 그래서 이 문제는 “시작점에서 가장 먼 귤까지의 거리”를 구하는 문제로 바꿔 읽을 수 있습니다. 같은 시각에 썩는 칸들, 즉 시작점에서 거리가 같은 칸들의 묶음을 레벨(level)이라고 부릅니다. (1, 0)과 (0, 1)이 레벨 1, (1, 1)과 (0, 2)가 레벨 2입니다.

큐로 한 레벨씩 나눈다

코드로 옮기려면 “이번 1분에 이웃을 썩게 할 귤”을 모아 둘 곳이 필요합니다. 먼저 넣은 것을 먼저 꺼내는 자료구조인 큐(queue)를 씁니다.

처음부터 썩어 있는 귤을 모두 queue에 넣습니다.
1분이 시작되면 queue의 귤을 앞에서부터 하나씩 꺼내, 상하좌우의 싱싱한 귤을 썩게 합니다.
새로 썩은 귤은 이번 1분 안에는 퍼뜨리지 않고 next에 모아 둡니다. 1분이 끝나면 next가 새 queue가 됩니다.
싱싱한 귤이 남지 않을 때까지 2~3을 되풀이합니다.

3번에서 새로 썩은 귤을 바로 퍼뜨리지 않고 next에 모으기 때문에, 한 번 반복할 때마다 정확히 한 레벨이 처리됩니다. 이렇게 시작점에서 가까운 레벨부터 옆으로 모두 훑은 뒤 다음 레벨로 넘어가는 탐색을 너비 우선 탐색(BFS, breadth-first search)이라고 합니다. 한 레벨의 너비(breadth)를 먼저 다 본다는 뜻입니다.

썩은 귤이 처음부터 여러 개라면 1번에서 모두 queue에 넣습니다. 여러 곳이 같은 0분에서 출발해 동시에 번지는 모습이 그대로 한 레벨이 됩니다.

DFS와 무엇이 다른가

DFS 플러드 필의 깊이 우선 탐색(DFS)도 이어진 칸을 모두 둘러보지만, 한 방향으로 갈 수 있는 데까지 먼저 들어갑니다. 같은 격자에서 (0, 0)부터 DFS로 들어가면 아래 (1, 0) → 오른쪽 (1, 1) → 아래 (2, 1) → 오른쪽 (2, 2)까지 내려간 뒤 돌아와서야 (1, 1)의 위쪽 (0, 1)에 닿습니다. 아래 그림은 칸마다 DFS로 몇 번째 깊이에서 닿았는지 적은 것이고, 실제로 썩는 시각과 다른 칸이 빨간색입니다.

(0, 1)은 (0, 0) 바로 옆이라 1분에 썩는데, DFS는 돌아서 닿았기 때문에 깊이가 3입니다. DFS의 깊이는 “처음 닿았을 때 거쳐 온 길이”일 뿐 가장 짧은 거리가 아닙니다. 이 예제에서는 가장 늦은 칸이 둘 다 4라 답이 우연히 같지만, 왼쪽 위만 썩고 나머지가 모두 싱싱한 3×3 격자라면 DFS 깊이는 8까지 가고 실제 답은 4입니다.

BFS는 가까운 레벨을 모두 마친 뒤에야 다음 레벨로 넘어가므로, 어떤 칸에 처음 닿은 레벨이 곧 그 칸까지의 가장 짧은 거리입니다. 최단 거리나 최소 시간을 물을 때 BFS를 쓰는 이유가 이것입니다.

직접 따라가 보기

아래 시각화는 이렇게 읽습니다.

칸 가운데 숫자는 격자 값이고, 귤이 썩으면 1이 2로 바뀌면서 오른쪽 위에 몇 분에 썩었는지 배지가 붙습니다.
노란 칸은 지금 이웃을 썩게 하는 귤이고, 파란 실선 칸은 이번 1분의 queue, 파란 점선 칸은 방금 썩어 next에서 기다리는 귤입니다.
화살표는 어느 귤이 어느 귤을 썩게 했는지를 가리킵니다.

변수 칸의 값은 아래 풀이 코드의 변수입니다.

minutes: 지금 몇 분째인지입니다.
fresh: 아직 남은 싱싱한 귤의 개수입니다. 0이 되면 반복을 멈춥니다.
queue, next: 이번 1분에 퍼뜨릴 귤과 다음 1분에 퍼뜨릴 귤입니다. queue의 노란 칸이 지금 꺼낸 귤입니다.

“다음”을 누르면 한 걸음씩 진행합니다. 2~3번째 단계에서 (0, 0)이 두 이웃을 썩게 하고, 4번째 단계에서 next에 있던 두 칸이 점선에서 실선으로 바뀌며 새 queue가 됩니다. 6번째 단계에서는 (0, 1)이 아래 (1, 1)을 건너뛰는데, 바로 앞 단계에서 (1, 0)이 먼저 썩혀 이미 2이기 때문입니다. 12번째 단계에서 fresh가 0이 되어 4를 돌려줍니다.

단계 1 / 12

변수

minutes: 0
fresh: 0남은 싱싱한 귤
queue
next
return: –

처음부터 썩어 있는 (0, 0)을 큐에 넣고, 싱싱한 귤 6개를 세며 시작합니다. "다음"을 눌러 보세요

지금 퍼뜨리는 귤
큐에 든 귤 (점선은 next)
퍼뜨리기를 마친 귤
마지막으로 썩은 귤

LeetCode 994 예제 1. 이웃은 아래·위·오른쪽·왼쪽 순서로 봅니다. 빌드할 때 BFS를 실제로 돌려 기록한 단계입니다.

위쪽에서 “꺼낼 때 표시”를 고르면, 귤을 next에 넣을 때가 아니라 나중에 queue에서 꺼낼 때 2로 표시하는 코드가 실행됩니다. 6번째 단계에서 (0, 1)이 아래 (1, 1)을 봤을 때 (1, 1)은 이미 next에 들어 있지만 값이 아직 1이라, 한 번 더 넣고 fresh도 한 번 더 줄입니다. 같은 일이 10번째 단계에서 되풀이되어 fresh가 -1이 되고, 격자에 싱싱한 귤이 남아 있는데도 -1을 돌려줍니다.

대표 문제 풀이

아래는 참고 풀이입니다. 반복문 안의 번호는 위 “큐로 한 레벨씩 나눈다”의 순서와 같고, 변수 이름은 시각화의 변수 칸과 같습니다.

var orangesRotting = function (grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 아래·위·오른쪽·왼쪽

  // ① 처음부터 썩은 귤을 모두 큐에 넣고, 싱싱한 귤을 센다
  let queue = [];
  let fresh = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }

  let minutes = 0;
  // ② 퍼뜨릴 귤과 싱싱한 귤이 모두 남아 있는 동안 1분씩 진행한다
  while (queue.length > 0 && fresh > 0) {
    minutes++;
    const next = [];
    for (const [r, c] of queue) {
      for (const [dr, dc] of moves) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (grid[nr][nc] !== 1) continue;
        // ③ 썩게 하는 순간 2로 바꿔, 같은 귤을 두 번 넣지 않는다
        grid[nr][nc] = 2;
        fresh--;
        next.push([nr, nc]);
      }
    }
    queue = next;
  }

  // ④ 끝까지 닿지 못한 귤이 있으면 -1
  return fresh === 0 ? minutes : -1;
};

①에서 처음부터 썩어 있는 귤을 전부 넣기 때문에 시작점이 여러 개여도 같은 코드로 풀립니다. ②의 while 한 바퀴가 1분, 곧 한 레벨이고, for...of로 이번 레벨의 queue를 다 돈 뒤 queue = next로 다음 레벨로 넘어갑니다. ③에서 next에 넣는 순간 2로 바꿔 두어야, 같은 1분 안에 다른 귤이 그 칸을 다시 보더라도 grid[nr][nc] !== 1에 걸려 건너뜁니다.

②의 조건에 fresh > 0이 있는 것도 이유가 있습니다. 이 조건 없이 queue가 빌 때까지 돌면, 마지막 귤이 썩은 뒤에도 그 귤을 꺼내 보는 빈 1분이 한 번 더 세어집니다. 예제 1에서 4가 아니라 5가 나오고, 썩을 귤이 처음부터 없는 예제 3([[0, 2]])에서도 0이 아니라 1이 나옵니다.

모든 칸은 많아야 한 번 queue에 들어가고, 꺼낼 때 이웃 네 칸을 보므로 시간은 O(행 × 열)입니다. queue와 next에 칸이 최대 칸 수만큼 담길 수 있어 공간도 O(행 × 열)입니다.

자주 하는 실수

큐에서 꺼낼 때 표시합니다. DFS에서 방문 표시를 칸에 들어갈 때 하듯, BFS에서는 큐에 넣을 때 표시해야 합니다. 꺼낼 때 표시하면 아래처럼 next에 들어갔지만 아직 1인 귤을 다른 귤이 한 번 더 넣게 됩니다.

for (const [r, c] of queue) {
  grid[r][c] = 2; // 꺼낼 때 표시
  for (const [dr, dc] of moves) {
    // … 격자 밖이면 continue
    if (grid[nr][nc] !== 1) continue;
    fresh--;
    next.push([nr, nc]);
  }
}

같은 귤이 두 번 들어가 fresh가 두 번 줄어드니, 예제 1에서 fresh가 0을 지나쳐 -1이 되고 답도 4가 아니라 -1이 나옵니다. 위 시각화의 “꺼낼 때 표시”가 이 코드입니다.

싱싱한 귤이 남았는지 확인하지 않습니다. 빈 칸에 막혀 끝까지 썩지 않는 귤이 있으면 답은 -1인데, ④ 없이 minutes를 그대로 돌려주면 이 경우를 놓칩니다. 예제 2에서는 왼쪽 아래 (2, 0)이 빈 칸으로 둘러싸여 어느 썩은 귤과도 이어지지 않습니다.

빨간 (2, 0)은 상하좌우가 빈 칸이나 격자 밖이라 끝까지 싱싱하게 남습니다.

④ 없이 돌리면 예제 2에서 -1이 아니라 5가 나옵니다. 마지막으로 썩는 (2, 2)는 4분에 썩지만, fresh가 끝까지 0이 되지 않으니 반복이 한 번 더 돌아 (2, 2)를 꺼내 보는 빈 1분까지 세기 때문입니다.

썩은 귤 하나에서만 시작합니다. 썩은 귤을 찾자마자 그 한 칸만 큐에 넣으면, 다른 썩은 귤에서 번지는 몫이 늦게 계산됩니다. [[2, 1, 1, 1, 2]]는 양 끝에서 동시에 번져 2분이면 모두 썩지만, 왼쪽 끝 하나에서만 출발하면 오른쪽 끝 바로 옆 칸까지 번지는 데 3분이 걸려 3을 돌려줍니다. 처음부터 썩어 있는 귤은 ①처럼 모두 큐에 넣어 0분 레벨로 함께 출발시킵니다.