너비 우선 탐색 (BFS: Breadth-First Search) 설명과 JavaScript 예제

너비 우선 탐색(BFS)은 그래프나 트리 구조에서 루트 노드 또는 시작 지점으로부터 가까운 노드부터 차례대로 탐색해 나가는 방식의 탐색 알고리즘입니다. 탐색이란 주어진 조건에 맞는 노드를 찾거나 모든 노드를 방문하는 과정을 의미하며, BFS는 이 중에서도 최단 경로를 찾는 데 효과적입니다. 일반적으로 큐(Queue) 자료구조를 이용해 구현되며, 알고리즘 문제 풀이뿐 아니라 실무에서도 널리 사용됩니다.

BFS는 특히 그래프의 연결성 확인, 최단 거리 계산, 최소 단계로의 전파 시뮬레이션 등 다양한 문제에서 활용됩니다. 깊이 우선 탐색(DFS)과 달리, 깊게 들어가기보다는 인접 노드를 우선 탐색한 뒤 그다음 깊이로 나아가는 것이 특징입니다.

---

1. 동작 원리

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 하나 꺼냄
3. 해당 노드에 인접한 모든 노드를 확인함
4. 아직 방문하지 않은 노드를 큐에 추가하고 방문 처리
5. 큐가 빌 때까지 2~4 과정을 반복

이 과정을 반복하면서 각 노드의 **깊이(거리)**를 기준으로 탐색을 수행합니다. BFS는 노드를 중복 없이 한 번씩만 방문하며, 방문 여부를 확인하기 위해 보통 Set 객체나 Boolean 배열을 사용합니다.

---

2. JavaScript 예제 (인접 리스트 기반)

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    if (!visited.has(node)) {
      console.log(node);
      visited.add(node);
      for (let neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: []
};

bfs(graph, 'A');

위 예제에서 그래프는 인접 리스트 형태로 표현됩니다. 각 키는 노드, 값은 연결된 이웃 노드 배열입니다. BFS 함수는 시작 노드를 인자로 받아 탐색을 시작하고, **console.log()**를 통해 방문 순서를 출력합니다.

• 큐를 통해 인접 노드를 순차적으로 탐색합니다.
• 중복 방문을 막기 위해 visited 집합을 사용합니다.
• 방문 순서는 A → B → C → D → E → F 순으로 계층적입니다.

---

3. BFS의 특징 및 활용 사례

• 최단 거리, 최소 이동 횟수 문제에 최적화
• 탐색 순서가 명확하여 디버깅 및 시각화에 유리함
• DFS에 비해 메모리 사용량이 다소 많을 수 있음 (큐에 노드들이 누적되기 때문)
• 반복문 기반으로 구현되며, 재귀를 사용하지 않음

활용 사례

• 미로 탐색
• 최단 경로 계산
• 전염병 확산 시뮬레이션
• 소셜 네트워크의 친구 추천
• 게임 AI에서 적 탐색

---

4. 시간 복잡도 분석

그래프 표현 방식	시간 복잡도
인접 리스트	O(V + E)
인접 행렬	O(V²)

• V: 정점 수 (Vertices)
• E: 간선 수 (Edges)

BFS는 각 노드와 간선을 한 번씩만 탐색하므로, 인접 리스트에서는 매우 효율적으로 작동합니다. 반면, 인접 행렬을 사용할 경우 불필요한 탐색이 발생하여 성능 저하가 발생할 수 있습니다.

---

결론: 언제 BFS를 사용할까?

너비 우선 탐색은 최단 거리 탐색, 폭발적인 전파, 계층 구조 처리 등 다양한 상황에 적합한 알고리즘입니다. DFS와는 탐색 방식이 다르기 때문에, 문제의 조건에 따라 어떤 방식을 사용할지 결정하는 것이 중요합니다. BFS는 정형화된 구조를 가지고 있으며, 논리적 흐름이 명확하다는 장점이 있어 알고리즘 학습 초기에 접하기에 매우 적합한 주제이기도 합니다.

BFS는 알고리즘 문제 풀이뿐만 아니라, 실제 경로 탐색, 웹 크롤러, 게임 AI, 네트워크 연결성 검사, 지형 분석 등 다양한 분야에서 널리 활용됩니다.