너비우선 탐색

너비우선 탐색

너비우선 탐색(BFS, Breadth First Search))이란 문자 그대로 탐색 순서에 있어서 깊이보다는 폭을 우선적으로 취한다.
너비우선 탐색은 주어진 노드로부터 거리 1인 노드를 모두 방문하고, 다음 거기서부터 거리 1인 노드, 즉 원래의 노드로부터 거리 2인 노드를 방문하고, 다시 거리 3의 노드를 방문한다.
이런 특성으로 인해, 만약에 목적지를 찾는 문제라면 그 목적지까지 가는 최단경로를 찾을 수 있다.
거리가 짧은 순서로 목적지를 찾아가기 때문이다.
깊이우선 탐색이 스택을 사용한다면, 너비우선 탐색은 큐를 사용한다.
그림에서 탐색이 시작되면 일단 출발지인 A를 큐에 삽입한다.
다음, 큐 프런트인 A를 제거하면서 A에 인접한 B,G를 모두 큐에 삽입한다.
다음, 현재의 큐 프런트인 B를 제거하면서 B와 인접한 C,E를 삽입한다.
다시 현재의 큐 프런트인 G를 제거하면서 G와 인접한 H를 삽입한다.
이러한 작업을 반복하면서 큐에서 제거된 노드를 순차적으로 나열하면 그것이 너비우선 탐색 순서가 된다.
너비우선 탐색도 깊이우선 탐색과 마찬가지로 “목적지까지 가는 길이 있는가?”라는 문제 해결에 사용될 수 있다.
예를 들어 위 그림에서 “A에서 출발하여 K까지 가는 길이 있는가?”라는 질문에 탐색을 실시하면 결국 마지막에 큐가 비게 되므로 “그런 길이 없다.”라고 답할 수 있다.
반대로 “A에서 출발하여 F까지 가는 길이 있는가?”라는 질문이라면 F가 큐 프런트인 상태에서 “그런 길이 있다.”라고 답할 수 있다.
결론적으로, 안 가본 새로운 도시만 큐에 삽입하고 안 가본 도시가 없을 때까지 모든 도시를 조직적으로 하나씩 방문하는 소모적 탐색의 한 방법이다.