sko.kr

너비 우선 탐색 (BFS)

algorithmsgraph-traversaltree-traversalbfsqueueshortest-path
By sko•10/7/2025•1 min read

너비 우선 탐색을 사용해야 할 때

BFS는 노드를 층별로 탐색해야 하거나 가중치 없는 그래프에서 최단 경로를 찾아야 할 때 사용합니다. 가장 일반적으로는 레벨 순회에 사용되지만, 다음과 같은 경우에도 적용할 수 있습니다:

  • 레벨 순서 트리 순회 (클래식 사용 사례)
  • 가중치 없는 그래프의 최단 경로 (층별 탐색으로 최적해 보장)
  • 시작점으로부터 거리 k에 있는 모든 노드 찾기
  • 그래프가 이분 그래프인지 확인 (같은 그룹 내의 두 노드가 연결되지 않은 두 그룹으로 노드를 분할할 수 있음 - 교대로 층에 노드를 색칠하여 수행)
  • 웹 크롤링 (더 깊이 가기 전에 같은 깊이의 링크를 탐색)
  • 소셜 네트워크 분석 (n차 분리 내에서 연결 찾기)
  • 더 멀리 이동하기 전에 현재 "거리"에서 모든 가능성을 탐색해야 하는 모든 문제

예제 문제

회사 조직도: 트리로 표현된 회사 계층이 주어졌을 때, 보고 구조를 이해하기 위해 모든 직원을 레벨별로 출력합니다.

        CEO
       /   \
     CTO   CFO
    /  \     \
  Dev1 Dev2  Acc1

Level 0: CEO
Level 1: CTO, CFO
Level 2: Dev1, Dev2, Acc1

이것은 관리 계층을 명확하게 보여줍니다 - 먼저 CEO의 모든 직접 보고자, 그다음 그들의 모든 직접 보고자, 이런 식으로 계속됩니다.

가장 중요한 통찰력

BFS는 거리 d+1의 어떤 노드보다도 먼저 거리 d의 모든 노드를 탐색합니다 - 그리고 큐(FIFO)를 사용함으로써, 노드가 발견된 정확한 순서로 처리되는 것이 보장되며, 이는 자동으로 레벨별 탐색과 가중치 없는 그래프에서의 최단 경로를 제공합니다.

멘탈 노트: 알고리즘의 천재성은 큐의 FIFO 속성에 있습니다. 노드의 이웃을 발견하면, 그들은 큐의 뒤쪽으로 갑니다. 이는 현재 레벨의 모든 노드가 다음 레벨의 어떤 노드보다도 먼저 처리된다는 것을 의미합니다. 극장을 줄별로 채우는 것과 같습니다 - 2번째 줄이 완전히 찰 때까지 3번째 줄을 시작할 수 없습니다.

결정 프레임워크

모든 노드에서 하나의 간단한 결정에 직면합니다:

  • 현재 노드를 처리 (방문한 것으로 표시)
  • 방문하지 않은 모든 이웃을 미래 탐색을 위해 큐에 추가

큐가 순서를 강제합니다 - 언제 노드를 처리할지 결정하는 것은 당신이 아니라, FIFO 구조가 그것을 수행합니다.

코드

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function bfs(root) {
  // 빈 트리 처리
  if (root == null) {
    return;
  }

  // 루트 노드로 큐 초기화
  const queue = [root];
  let level = 0;

  // 레벨별로 노드 처리
  while (queue.length > 0) {
    // 현재 레벨 크기 캡처 - 이것이 핵심!
    const levelSize = queue.length;
    const currentLevelNodes = [];

    // 현재 레벨의 모든 노드 처리
    for (let i = 0; i < levelSize; i++) {
      // 결정 프레임워크: 현재 노드 처리
      const currentNode = queue.shift();
      currentLevelNodes.push(currentNode.val);

      // 결정 프레임워크: 방문하지 않은 이웃(자식)을 큐에 추가
      if (currentNode.left != null) {
        queue.push(currentNode.left);
      }
      if (currentNode.right != null) {
        queue.push(currentNode.right);
      }
    }

    // 현재 레벨 출력
    console.log(`Level ${level}: ${currentLevelNodes.join(", ")}`);
    level++;
  }
}

// 회사 조직도를 사용한 예제
const ceo = new TreeNode("CEO");
const cto = new TreeNode("CTO");
const cfo = new TreeNode("CFO");
const dev1 = new TreeNode("Dev1");
const dev2 = new TreeNode("Dev2");
const acc1 = new TreeNode("Acc1");

ceo.left = cto;
ceo.right = cfo;
cto.left = dev1;
cto.right = dev2;
cfo.right = acc1;

bfs(ceo);
// 출력:
// Level 0: CEO
// Level 1: CTO, CFO
// Level 2: Dev1, Dev2, Acc1

의문 해소

일반적인 의문: "왜 DFS(깊이 우선 탐색)를 사용해서 트리를 순회할 수 없을까? 어차피 결국 모든 노드를 방문하지 않나? 레벨 순회에서 BFS가 특별한 이유는 무엇인가?"

이것은 자연스러운 질문입니다. BFS와 DFS 모두 모든 노드를 방문하기 때문입니다. 특정 문제에서 BFS가 필수적인 이유를 살펴보겠습니다.

DFS가 작동할 수 있다고 생각할 수 있는 이유

우리의 회사 조직도를 고려해보세요. DFS로, 다음과 같이 생각할 수 있습니다:

  • "먼저 깊이 갈 것이다: CEO → CTO → Dev1, 그런 다음 백트랙"
  • "결국 모든 노드를 방문할 것이므로 차이가 무엇인가?"
  • "깊이를 추적하고 레벨별로 노드를 그룹화할 수 없을까?"

이러한 생각이 핵심을 놓치는 이유

핵심 깨달음: BFS는 단순히 모든 노드를 방문하는 것이 아닙니다 - 고유한 보장을 제공하는 특정 순서로 방문합니다!

BFS 대 DFS 순회 순서를 비교해 봅시다:

BFS 순서: CEO → CTO → CFO → Dev1 → Dev2 → Acc1
(레벨 0의 모든 것, 그다음 레벨 1의 모든 것, 그다음 레벨 2의 모든 것)

DFS 순서: CEO → CTO → Dev1 → Dev2 → CFO → Acc1
(먼저 깊이 가고, 레벨 간에 점프)

구체적인 예: 최단 경로 찾기

가중치 없는 그래프에서 CEO에서 Acc1까지의 최단 경로를 찾는다고 상상해보세요:

BFS의 경우:

단계 1: CEO 처리 (거리 0)
단계 2: CTO, CFO 처리 (거리 1) - CFO 발견!
단계 3: CFO의 자식 처리 - 거리 2에서 Acc1 발견!

DFS의 경우 (더 긴 경로를 취할 수 있음):

단계 1: CEO 처리
단계 2: CTO 처리 (왼쪽으로 이동)
단계 3: Dev1 처리 (더 깊이 왼쪽으로 이동)
단계 4: CTO로 백트랙
단계 5: Dev2 처리
단계 6: CEO까지 전체 백트랙
단계 7: 마침내 CFO 처리
단계 8: Acc1 처리

DFS는 노드를 찾을 수 있지만, 최단 경로를 통한 것임을 보장하지 않습니다!

왜 큐가 필수적인가

BFS의 큐는 "세대 추적기"처럼 작동합니다:

  1. 세대 0 (루트): 큐에 CEO만
  2. 세대 1 (자식): CTO와 CFO가 큐에 추가
  3. 세대 2 (손자): Dev1, Dev2, Acc1이 큐에 추가

FIFO 속성은 다음을 보장합니다:

  • 모든 세대 1 노드가 어떤 세대 2 노드보다도 먼저 처리됨
  • 이것은 DFS의 스택(LIFO) 또는 재귀 호출 스택으로는 불가능함

레벨 크기 트릭

레벨별 처리를 가능하게 하는 BFS의 중요한 라인:

const levelSize = queue.length; // 현재 레벨의 크기 스냅샷

이것은 현재 레벨에 몇 개의 노드가 있는지 정확히 캡처합니다. 처리하는 동안 큐에 새 노드를 추가하고 있지만, 한 레벨이 끝나고 다음이 시작되는 지점을 정확히 알 수 있습니다.

이것이 정확성을 보장하는 이유:

  • 레벨 처리를 시작할 때, 큐에는 그 레벨의 노드만 포함됨
  • 각 노드를 처리할 때, 그 자식(다음 레벨)을 큐에 추가
  • 하지만 levelSize개의 노드만 처리하므로, 현재 레벨이 완료될 때 정확히 멈춤
  • 큐는 이제 다음 레벨의 노드만 포함함

이 우아한 메커니즘은 BFS가 레벨 순회와 최단 경로를 보장할 수 있는 이유입니다. 이는 깊이 우선의 특성 때문에 DFS가 근본적으로 제공할 수 없는 것입니다.

← Back to Blog