BFS · Breadth-first search
너비 우선 탐색
가까운 점부터 큐의 순서대로 방문해요
A에서 각 점까지의 최단거리를 구해요
지금 보는 점—
방문한 점0 / 6
현재 위치비교 대상확인한 값
예제 코드
C++
<vector> <queue>std::vector<int> bfs( const std::vector<std::vector<int>>& graph, int start) { std::vector<int> distance(graph.size(), -1); std::queue<int> queue; distance[start] = 0; queue.push(start); while (!queue.empty()) { int current = queue.front(); queue.pop(); for (int neighbor : graph[current]) { if (distance[neighbor] == -1) { distance[neighbor] = distance[current] + 1; queue.push(neighbor); } } } return distance;}Python
from collections import dequedef bfs(graph, start): distance = [-1] * len(graph) distance[start] = 0 queue = deque([start]) while queue: current = queue.popleft() for neighbor in graph[current]: if distance[neighbor] == -1: distance[neighbor] = distance[current] + 1 queue.append(neighbor) return distance예제의 A~F는 코드에서 0~5번이에요. graph에는 각 번호의 이웃을 순서대로 담아요.
시작하기
가까운 점부터 살펴봐요
A에서 시작해요. 한 간선을 건너는 비용이 같으므로 큐의 순서대로 최단거리를 구할 수 있어요.
사용 조건
간선마다 이동 비용이 같은 그래프에서 시작점부터의 최단거리를 구할 때 사용할 수 있어요. 연결된 점을 빠짐없이 찾는 데도 사용해요.
먼저 알아두면 좋아요
큐는 먼저 넣은 값을 먼저 꺼내요. 그래프는 점과 점 사이의 연결을 나타내요. 예제는 양방향 연결이에요.
동작 원리
시작점의 거리를 0으로 기록하고 큐에 넣어요. 큐의 앞에서 점을 꺼낸 뒤 아직 발견하지 않은 이웃을 확인해요.
이웃의 거리는 현재 거리 + 1이에요. 큐에 넣는 즉시 발견 표시를 남겨 중복 삽입을 막아요. 큐의 순서 덕분에 가까운 점부터 처리해요.
- 시간
- O(V + E) · 인접 리스트에서 점과 간선을 확인해요
- 추가 공간
- O(V) · 거리 배열과 큐를 사용해요
주의할 점
- 큐에서 꺼낼 때가 아니라 넣을 때 발견 표시를 남겨요.
- 이동 비용이 다르면 이 거리 계산을 그대로 사용할 수 없어요. 방문할 수 없는 점의 거리는 −1로 남아요.