Motivation
Coddy의 너비 우선 탐색 - 그래프 알고리즘 코스 레슨 — 9개 중 2번째.
BFS는 **큐**(queue, 선입선출)를 사용하여 정점이 발견된 순서대로 처리되도록 하며, 이를 통해 층별 탐색(layer-by-layer exploration)을 수행합니다.
왜 BFS를 배워야 할까요?
- 최단 경로: 가중치가 없는 그래프에서 BFS는 시작점부터 다른 모든 정점까지의 가장 적은 간선을 가진 경로를 찾습니다.
- 단순하고 선형적임: 큐와 방문 표시(visited marker)를 사용하여 O(V + E)의 시간 복잡도로 실행됩니다.
- 어디에서나 사용됨: 네트워크의 최단 홉, 워드 래더(word ladders), 미로 찾기, 트리의 레벨 순서 순회(level-order tree traversal)는 모두 BFS를 사용합니다.
DFS와 마찬가지로, 결과의 예측 가능성을 위해 정점의 이웃들을 오름차순으로 큐에 넣습니다(enqueue).
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
