너비 우선 탐색

핵심 개념

너비 우선 탐색(breadth-first search, BFS)은 출발 노드에서 가까운 노드부터 층층이 방문합니다. 출발 노드를 거리 0으로 표시하고, 그 이웃을 거리 1로, 이웃의 아직 방문하지 않은 이웃을 거리 2로 표시하는 식입니다. 물결이 퍼지듯 한 층을 모두 처리한 뒤에 다음 층으로 넘어갑니다.

순서를 지키는 도구가 큐(queue)입니다. 큐는 먼저 넣은 것을 먼저 꺼내는 줄(FIFO)입니다. ① 출발 노드에 방문 표시를 하고 큐에 넣습니다. ② 큐 맨 앞의 노드를 꺼냅니다. ③ 그 노드의 이웃 중 방문 표시가 없는 노드에 ‘꺼낸 노드의 거리+1’을 적고, 표시한 뒤 큐 뒤에 넣습니다. ④ 큐가 빌 때까지 ②와 ③을 반복합니다. 넣을 때 표시해야 같은 노드가 큐에 두 번 들어가지 않습니다.

가중치가 없는 그래프에서 BFS가 노드에 처음 붙인 거리는 출발 노드로부터의 최단 홉 거리입니다. 가까운 층을 모두 처리한 뒤에야 다음 층을 열기 때문입니다. 노드와 엣지를 한두 번씩만 보므로 계산량은 N+E에 비례합니다. 다만 엣지마다 가중치가 다르면 홉 수가 적은 경로가 비용도 작다는 보장이 없으므로 13회차의 다익스트라 알고리즘을 씁니다.

작은 예제로 따라가기

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

풀이와 확인 표시는 이 브라우저에 저장됩니다.