15. BFS

BFS

빠른 설명

BFS(Breadth First Search, 너비 우선 탐색)는 시작점에서 가까운 정점부터 차례대로 방문하는 탐색이다. 큐를 사용하며, 가중치가 없는 그래프의 최단거리를 구할 때 표준적으로 쓴다.

언제 쓰는가

• 최단 이동 횟수
• 격자에서 가장 가까운 칸 찾기
• 단계별로 퍼지는 시뮬레이션
• 연결 여부 확인

시간복잡도

• 인접 리스트 기준: $O(V+E)$

참고자료

• CP-Algorithms - Breadth First Search
• Wikipedia - Breadth-first search
• GeeksforGeeks - Breadth First Search
• 나무위키 - 너비 우선 탐색

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3},
        {0, 4},
        {1},
        {2},
    };
 
    int n = graph.size();
    vector<int> dist(n, -1);
    queue<int> q;
 
    dist[0] = 0;
    q.push(0);
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int next : graph[cur]) {
            if (dist[next] == -1) {
                dist[next] = dist[cur] + 1;
                q.push(next);
            }
        }
    }
 
    for (int d : dist) cout << d << ' ';
}

Python 코드

from collections import deque
 
graph = [
    [1, 2],
    [0, 3],
    [0, 4],
    [1],
    [2],
]
 
dist = [-1] * len(graph)
q = deque([0])
dist[0] = 0
 
while q:
    cur = q.popleft()
    for nxt in graph[cur]:
        if dist[nxt] == -1:
            dist[nxt] = dist[cur] + 1
            q.append(nxt)
 
print(dist)