BFS는 그래프나 트리의 자료구조에 적용할 수 있는 맹목적 탐색 알고리즘이다. 맹목적 탐색은 주어진 정보에 따라 효율적인 탐색을 실시하는 것이 아닌 이미 정해진 순서로 탐색을 실시하는 방법으로 실용적으로 따져볼 때 매우 비효율적인 알고리즘이지만 구현이 쉽고 간단한 문제에 한해 아주 유용하다. 이름 그대로 트리에서 노드를 깊게 파고드는 것보다 한 계층을 순차적으로 모두 살펴보는 것을 우선하는 알고리즘이다. BFS는 Queue로 구현할 수 있다.
1. 탐색을 시작할 정점을 Queue에 삽입한다.
2. Queue가 비었다면 '9'로 이동한다.
3. Queue의 가장 위에 있는 정점이 현재 탐색 중인 정점이다.
4. 탐색 중인 정점이 찾으려는 자료이면 '8'로 이동한다.
5. 탐색 중인 정점과 연결된 정점을 Queue에 삽입한다.
6. 탐색 중인 정점을 체크하고 Queue에서 삭제한다. (중복 탐색 방지)
7. '2'로 이동한다.
8. 탐색 중인 정점을 출력한다.
9. 끝
Queue는 선입선출(First In First Out, FIFO) 자료구조이기 때문에 먼저 삽입된 자료를 먼저 탐색한다. 덕분에 유용한 특징이 몇 가지 있는다. 먼저 큐에 대기 중인 정점들은 무조건 연속된 2개의 계층 안에 속하는 정점들이다. 최초 탐색 정점의 레벨을 1, 거기서 연결된 정점들의 레벨을 2, 레벨 2의 정점들에 연결된 정점들의 레벨을 3 이렇게 반복해 N 레벨의 정점까지 정의해보면 N 미만의 L 레벨 정점이 현재 큐의 맨 앞에 있는 정점이라면 큐 안에는 최대 L + 1 레벨의 정점만 있을 수 있다. L + 2 레벨 정점부터는 L + 1 레벨의 정점에서 탐색될 수 있기 때문이다. 그리고 이런 이유로 탐색 깊이가 최단 거리임이 보장된다.
너무 단순한 알고리즘이기 때문에 치명적인 단점도 있다. 만약 탐색 범위 안에 해가 없다면 모든 정점을 다 돌아본 후에 탐색이 실패했음을 알게된다. 그리고 경로가 조금만 길어져도 탐색 시간이 급증하며 노드가 많아져서 탐색할 자료가 무한에 가까워지면 탐색이 결국 불가능해진다.
백준 예제
