핵심 인사이트 (3줄 요약)
- 본질: BFS (Breadth-First Search)는 시작 정점에서 가까운 이웃부터 단계별(레벨별)로 탐색하는 그래프 알고리즘으로, 큐 (Queue) 자료구조를 사용한다.
- 가치: 비가중치 그래프에서 시작 정점에서 모든 정점까지의 최단 경로 (간선 수 최소)를 O(V+E) 시간에 보장한다.
- 판단 포인트: 최단 경로 보장이 필요하면 BFS, 가중치가 있으면 다익스트라로 전환하며 0-1 BFS, 다중 출발 BFS 등 변형을 파악해야 한다.
Ⅰ. 개요 및 필요성
너비 우선 탐색 (BFS, Breadth-First Search)은 시작 정점을 기준으로 거리 1인 정점을 모두 방문하고, 그 다음 거리 2인 정점을 방문하는 방식으로 동심원을 그리며 퍼져 나가는 탐색이다.
| 특성 | 내용 |
|---|---|
| 시간 복잡도 | O(V+E) |
| 공간 복잡도 | O(V) (큐 + 방문 배열) |
| 구현 방식 | 큐 (Queue, FIFO) |
| 최단 경로 보장 | 비가중치 그래프에서 보장 |
BFS가 적합한 상황:
- 비가중치 그래프에서 최단 경로 탐색
- 이분 그래프 (Bipartite Graph) 판별
- 최소 단계 수 탐색 (퍼즐, 게임 최소 이동)
- 다중 출발 BFS (여러 소스에서 동시 확산)
📢 섹션 요약 비유: BFS는 돌멩이를 물에 던졌을 때 퍼지는 파문과 같다. 가장 가까운 물결부터 퍼지고, 같은 거리의 지점은 동시에 도달한다.
Ⅱ. 아키텍처 및 핵심 원리
기본 동작 순서
그래프: A ─ B ─ D
| |
C ───── E
BFS 시작: A (목표: 최단 경로 탐색)
레벨 0: [A] → 방문: A
레벨 1: [B, C] → 방문: B, C
레벨 2: [D, E] → 방문: D, E (A-B-D, A-C-E 각 최단 거리 2)
방문 순서: A → B → C → D → E
ASCII 다이어그램 — BFS 큐 진행과 레벨
┌──────────────────────────────────────────────────────────┐
│ 그래프: A ─ B ─ D BFS 큐 변화: │
│ │ │ │
│ C ───── E 초기 큐: [A] │
│ │
│ dist[A]=0 A 꺼냄 → [B, C] 삽입 │
│ dist[B]=1 dist[C]=1 B 꺼냄 → [C, D] 삽입 │
│ dist[D]=2 dist[E]=2 C 꺼냄 → [D, E] 삽입(D중복제거)│
│ D 꺼냄 → [E] (E이미 큐에) │
│ 레벨별 탐색: E 꺼냄 → [] 완료 │
│ 레벨 0: A │
│ 레벨 1: B, C 최단 거리 배열: │
│ 레벨 2: D, E dist = {A:0, B:1, C:1, │
│ D:2, E:2} │
└──────────────────────────────────────────────────────────┘
최단 경로 복원
BFS는 parent[] 배열로 각 정점의 이전 정점을 기록하여 경로를 역추적한다.
parent[B] = A, parent[D] = B
D까지 경로: D → B → A → 역순: A → B → D
이분 그래프 판별 (Bipartite Check)
BFS로 정점을 2가지 색으로 교대 칠할 때 인접 정점이 같은 색이면 이분 그래프가 아님.
색 0 ─── 색 1 ─── 색 0 ─── ...
A(0) ─ B(1) ─ D(0) → 성공
A(0) ─ B(1) ─ A(0)? 같은 색 인접 → 비이분 = 홀수 사이클 존재
| 알고리즘 응용 | 방법 | 결과 |
|---|---|---|
| 최단 경로 | dist[] 배열 갱신 | 간선 수 최소 경로 |
| 이분 그래프 판별 | 2-색칠 BFS | 이분 여부 확인 |
| 다중 출발 BFS | 여러 소스를 초기 큐에 삽입 | 모든 소스 동시 확산 |
| 0-1 BFS | 가중치 0: 앞에 삽입, 1: 뒤에 삽입 (deque) | 0/1 가중치 최단 경로 |
📢 섹션 요약 비유: 이분 그래프 판별은 반 학생들을 두 팀으로 나눌 때 친한 친구끼리는 다른 팀에 배치하는 작업이다. 홀수 명이 서로 친하면 두 팀으로 나눌 수 없다.
Ⅲ. 비교 및 연결
BFS vs DFS vs 다익스트라
| 항목 | BFS | DFS | 다익스트라 |
|---|---|---|---|
| 데이터 구조 | 큐 (FIFO) | 스택 (LIFO) | 우선순위 큐 |
| 최단 경로 | 비가중치 보장 | 보장 안 됨 | 비음수 가중치 보장 |
| 시간 복잡도 | O(V+E) | O(V+E) | O((V+E)log V) |
| 적용 그래프 | 비가중치 | 모든 그래프 | 비음수 가중치 |
| 이분 판별 | 가능 | 가능 | 해당 없음 |
| 레벨 탐색 | 자연스러움 | 비효율 | 해당 없음 |
📢 섹션 요약 비유: BFS는 회사에서 직급별로 보고받는 구조다. 1단계(팀장)를 모두 처리하고, 2단계(부장)를 처리하는 방식. DFS는 한 라인을 CEO까지 올라가 내려오는 방식이다.
Ⅳ. 실무 적용 및 기술사 판단
실무 시나리오
시나리오 1: 소셜 네트워크 6단계 법칙 검증
- Facebook의 "몇 단계 건너 아는 사람" 탐색
- BFS로 레벨별 탐색 → 최소 연결 단계 수 계산
시나리오 2: 게임 AI 최단 경로 (RPG, 퍼즐)
- 체스 나이트의 최소 이동 횟수 (모든 이동 비용이 동일)
- BFS로 시작 위치에서 목적지까지 최소 이동 수 계산
시나리오 3: 네트워크 라우팅 (홉 수 최소화)
- 방화벽에서 특정 노드까지 최소 홉 수 경로
- OSPF 프로토콜의 최단 경로 계산 기반
시나리오 4: 다중 출발 BFS (Multi-Source BFS)
- 화재 시뮬레이션: 여러 화재 발원지에서 동시에 BFS 확산
- 모든 셀까지의 최단 거리를 O(V+E)에 계산
기술사 판단 포인트
| 상황 | 선택 | 이유 |
|---|---|---|
| 비가중치 최단 경로 | BFS | 레벨별 탐색 = 최단 거리 보장 |
| 가중치 최단 경로 | 다익스트라 | BFS는 가중치 처리 불가 |
| 최소 단계 수 탐색 | BFS | 스텝 = 레벨 = 거리 |
| 이분 그래프 판별 | BFS/DFS 모두 | 2-색칠 알고리즘 |
| 0/1 가중치 그래프 | 0-1 BFS (deque) | 다익스트라보다 O(V+E) 효율 |
📢 섹션 요약 비유: BFS는 지진 대피 시 가장 가까운 대피소를 찾는 알고리즘이다. 지진 진원지(출발점)에서 동심원으로 퍼져나가 각 건물까지 최소 이동 거리를 계산한다.
Ⅴ. 기대효과 및 결론
BFS (Breadth-First Search)는 비가중치 그래프에서 최단 경로를 O(V+E) 시간에 보장하는 표준 알고리즘이다. 다중 출발 BFS, 0-1 BFS, 이분 그래프 판별 등 다양한 변형으로 실무 문제에 직접 적용된다.
핵심 결론: 비용이 균등한 환경에서 "가장 빠른 도달 경로"를 구할 때 BFS는 항상 정확한 답을 준다. 비용이 불균등해지는 순간 다익스트라로 전환하라.
📢 섹션 요약 비유: BFS는 물이 흘러내리는 방식과 같다. 중력이 균등하면(비가중치) 물은 항상 가장 짧은 경로로 흐른다. 지형이 울퉁불퉁하면(가중치) 다익스트라가 필요하다.
📌 관련 개념 맵
| 개념 | 관계 | 설명 |
|---|---|---|
| DFS (Depth-First Search) | 대안 | 위상 정렬, SCC에 적합 |
| 다익스트라 (Dijkstra) | 확장 | 가중치 그래프 최단 경로 |
| 이분 그래프 (Bipartite) | 응용 | BFS 2-색칠로 판별 |
| 다중 출발 BFS | 변형 | 여러 소스 동시 확산 |
| 0-1 BFS | 변형 | 0/1 가중치 deque 활용 |
| OSPF 프로토콜 | 활용 | 네트워크 최단 경로 라우팅 |
📈 관련 키워드 및 발전 흐름도
[그래프 (Graph)]
│
▼
[큐 (Queue)]
│
▼
[BFS (Breadth-First Search)]
│
▼
[최단 경로 (Shortest Path)]
이 흐름도는 그래프 탐색이 큐를 통해 BFS로 구현되고 최단 경로 문제로 확장되는 흐름을 보여준다.
👶 어린이를 위한 3줄 비유 설명
- 💧 BFS는 물웅덩이에 돌을 던졌을 때 번지는 파문처럼, 출발점에서 가까운 곳부터 차례로 퍼져나간다.
- 🎯 모든 이동 거리가 같을 때(계단을 한 칸씩 오르는 것처럼), BFS는 항상 가장 짧은 경로를 찾아준다.
- 🚗 하지만 도로마다 통행 요금이 다른 유료 도로에서는 BFS가 아닌 다익스트라가 필요하다.