<aside> 💡 너비 우선 탐색도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

</aside>

너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다.

너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.

너비 우선 탐색 과정

1. 시작 노드를 큐에 저장
2. 맨 앞의 값을 꺼냄
3. 문제에서 요구하는 연산을 수행
4. 인접 노드를 큐에 저장
5. 탐색이 끝난 노드를 버림
6. 다음 노드를 꺼내 큐가 빌 때까지 2~6 반복

너비 우선 탐색의 핵심 이론

BFS의 용도

1. 최단 경로 탐색
2. 네트워크 탐색
3. 퍼즐 문제

[1260] DFS와 BFS 프로그램