🚀 그래프 탐색 알고리즘 - 너비 우선 탐색!?

❓그래프 탐색이란?

저번에 깊이 우선 탐색을 공부하면서 까먹을까봐 한번 더 적어보자면!!

 

네트워크가 어떻게 퍼져나가는지, 지도가 어떻게 연결되어 있는지, 소셜 네트워크에서 누가 누구와 이어져 있는지 등

복잡한 관계를 이해하고 문제를 해결하는 핵심 도구가 바로 그래프 탐색이다.

그래프 탐색은 정점(Node) 과 간선(Edge) 으로 이루어진 그래프에서
특정 시작점으로부터 다른 노드를 차례로 방문하는 과정을 말한다.

 

👉 목적: 원하는 노드나 경로를 찾거나, 연결 관계를 분석하기 위해
👉 응용: 네트워크 감염 추적, 미로 길 찾기, 소셜 네트워크 관계 분석, 전력망 탐색, 지도 탐색 등

 

그래프 탐색에는 크게 두 가지 대표적인 방법이 있다.

1. 깊이 우선 탐색 (DFS, Depth First Search)
2. 너비 우선 탐색 (BFS, Breadth First Search)

오늘은 이 중에서, 레벨 순서대로 탐색하는
✨ 너비 우선 탐색(BFS) 에 대해 정리해 보도록 하겠다!

 

 

 

📌 BFS란 무엇인가?

너비 우선 탐색(Breadth-First Search)은 그래프나 트리 구조에서 

가까운 노드(혹은 정점)부터 차례로 탐색하는 알고리즘이다

 

즉, 깊게 파고들기보다 넓게, 같은 레벨의 노드들을 먼저 탐색하는 방식!!

 

 

 

⚙️ 동작 원리

BFS는 큐(Queue) 자료구조를 사용한다

큐는 FIFO(First In, First Out) - 먼저 들어온 데이터가 먼저 나가는 구조!!

 

🔩 탐색 과정

1. 시작 노드를 큐에 추가
2. 큐에서 노드를 꺼냄
3. 해당 노드의 인접한 노드 중 방문하지 않은 노드를 큐에 추가
4. 큐가 빌 때까지 2~3번을 반복

 

 

💻 코드 예시

function bfs(graph, start) {
  const visited = new Set();   // 방문한 노드 저장
  const queue = [start];   // 탐색용 큐

  while (queue.length > 0) {
    const node = queue.shift();   // 큐에서 하나 꺼냄
    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);   // 방문 순서 출력

      // 인접 노드 검색
      const neighbors = graph[node];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

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

bfs(graph, "A");
// 출력: A B C D E F

 

 

 

📊 BFS의 특징

 

⏱️ 시간 복잡도

• O(V + E)
  (V: 정점 개수, E: 간선 개수)
• 모든 정점과 간선을 한 번씩 방문하기 때문에 DFS와 동일한 시간 복잡도를 가진다

 

💾 공간 복잡도

• O(V)
• 큐(Queue)에 최악의 경우 모든 노드가 들어갈 수 있기 때문
• 트리의 경우, 가장 넓은 레벨의 노드 수가 큐에 저장될 수 있다

 

✅ 장점

• 최단 경로를 보장함(가중치가 없는 그래프의 경우)
• 레벨(깊이)별로 탐색하므로 탐색 순서를 직관적으로 파악 가능
• 병렬적 탐색 구조로 확장하기 쉬움
• 미로, 최단 거리, 네트워크 탐색 등에 활용도가 높음

 

⚠️ 단점

• 메모리 사용량이 많을 수 있음(큐에 노드가 많이 쌓임)
• 깊이가 얕고 폭이 넓은 그래프일수록 비효율적
• 가중치가 있는 그래프에서는 최단 경로를 보장하지 않음(-> 다익스트라 알고리즘 필요)

 

 

💡 실전 팁

• 큐 성능 최적화: JavaScript에서 Array.shift()는 O(n)이므로, 인덱스 포인터 방식이나 Deque 구조를 사용하면 성능을 개선할 수 있다.
• 방문 체크 필수: 큐에 노드를 넣을 때 바로 방문 표시를 해야 중복 방문을 방지할 수 있다
• 최단 거리 계산: distance 배열을 따로 두어 distance[next] = distance[current] + 1 식으로 관리하면 거리 계산이 명확해진다
• 좌표 기반 탐색: 2차원(미로, 지도) 문제에서는 dx, dy 배열을 활용해 상하좌우 탐색을 통일하면 코드가 깔끔해진다
• 레벨별 탐색 시 유용: BFS는 같은 깊이(레벨)의 노드를 한 번에 탐색하므로, “몇 단계 후” 같은 조건 판단이 쉽다
• 메모리 주의: 큐에 많은 노드가 쌓일 수 있으므로, 방문 처리를 제대로 하지 않으면 메모리 폭주가 발생할 수 있다

 

 

 

✅ 마무리

 

BFS는 그래프 탐색의 핵심 알고리즘으로, 최단 거리 계산 · 단계별 탐색 · 전파 시뮬레이션 등 다양한 문제에서 활용된다

 

특히 가중치가 없는 그래프에서는 최단 경로를 보장하기 때문에,
실무와 코딩 테스트 모두에서 반드시 익혀야 할 필수 알고리즘이다

 

처음에는 큐 구조와 방문 처리 방식이 낯설 수 있지만
한 번 익히면 그래프 탐색의 기초 체력을 키워주는 강력한 도구가 된다