너비 우선 탐색(BFS: Breadth First Search)

그래프를 탐색하는 보편적인 방법은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있습니다.
이번 시간에는 그 중 너비 우선 탐색에 대해 알아보겠습니다.
너비 우선 탐색은 그래프를 넓게 탐색하는 방법입니다. 예를 들어 보겠습니다.

---

[예시 그래프]

너비 우선 탐색의 알고리즘은
 1. 노드와 연결된 탐색하지 않은 모든 이웃 노드를 탐색한다.
 2. 방금 탐색한 노드들에 1번 과정을 실행한다.
입니다. 즉, 1번 2번을 모든 노드가 탐색될 때까지 번갈아가며 실행합니다.

이해를 돕기위해 위의 예시 그래프를 너비 우선 탐색(BFS)으로 탐색해 보겠습니다. 
시작 노드는 1번으로 하겠습니다.  

일단 시작 노드인 1번 노드를 탐색합니다. 그리고 1번 노드의 이웃 노드 중 탐색하지 않았던 노드들을 우선 모두 탐색합니다. 즉, 2번 3번 노드를 탐색합니다. 

방금 탐색한 2번, 3번 노드들의 이웃 중 탐색하지 않은 노드들을 모두 탐색합니다.
그러면 2번 노드의 이웃 노드인 4번, 5번 노드와 3번 노드의 이웃 노드들인 6번, 7번, 8번 노드들이 탐색됩니다.

앞에서 한 것과 같이 방금 탐색한 4, 5, 6, 7, 8번 노드들의 탐색하지 않은 이웃노드들을 모두 탐색합니다. 즉, 9번, 10번 노드를 방문합니다.

이제 9번, 10번 노드들의 이웃 노드 중 방문하지 않은 노드인 11번 노드를 방문합니다.
그러면 모든 노드들을 탐색했으므로 너비 우선 탐색을 종료합니다.

---

이제 너비 우선 탐색을 어떻게 구현하는지에 대해 알아보겠습니다.
모든 노드에 대해 같은 알고리즘을 적용하며 탐색하므로 재귀함수를 이용하여 구현할수도 있습니다.
그리고 큐를 이용해서도 너비 우선 탐색을 구현할 수 있습니다. 이 방법에 대해 상세히 알아보겠습니다.

그런데 깊이 우선 탐색은 왜 큐를 이용하여 구현할까요. 
큐는 데이터를 처리하는 방식이 FIFO(First In First Out)입니다. 즉, 먼저 입력된 자료들이 먼저 처리되는 선입선출 방식입니다.
너비 우선 탐색은 먼저 탐색한 노드들의 이웃 노드들을 모두 먼저 탐색합니다. 즉, 선입선출 방식과 같다고 볼 수 있습니다. 그러므로 큐가 너비 우선 탐색을 구현할 때 적절한 자료 구조라고 할 수 있습니다. 

구현시 큐에는 탐색해야 할 노드들을 저장해 줍니다. 너비 우선 탐색 시 탐색할 노드는 먼저 탐색했던 노드 즉, 큐의 front에 위치한 노드입니다. 이 노드의 탐색하지 않은 이웃 노드들을 큐에 모두 push합니다.

 

위의 그래프를 너비 우선 탐색했을 때 큐의 변화를 함께 살펴보겠습니다.
이 때, 노드들의 방문 여부를 알아보기 위한 bool형 check 배열이 필요합니다. 이 배열은 처음엔 false로 초기화 시켜주고 큐에서 x번 노드가 pop될 때 check[x]를 true로 바꿔서 탐색했다는 것을 표시해줍니다.

일단 시작 노드는 1번 이므로 큐에 1번 노드를 push 한 뒤 탐색을 시작합니다.
큐의 front인 1번 노드를 큐에서 꺼내면서 탐색하지 않은 이웃한 모든 노드들을 큐에 넣어줍니다. 그래서 위의 표에서 큐에 2, 3번 노드가 들어간 것을 볼 수 있습니다. 1번 노드를 큐에서 pop해주므로 check[x]를 true로 만들어줍니다.
8번 노드까지의 결과를 구할 수 있습니다. 이제 9번 노드가 pop될 때를 보겠습니다. 9번 노드가 pop될 때 check[9]는 false 즉, 아직 방문하지 않았으므로 9번 노드의 방문하지 않은 이웃 노드들을 큐에 넣어줍니다. 그림에서 보면 9번의 이웃 노드들은 4번, 5번 인데 이미 방문을 했으므로(check[4]와 check[5]가 true 이므로) 큐에 넣어주지 않습니다. 즉, 큐 안에 아무것도 push하지 않습니다.
그리고 다시 큐의 front에 있는 노드의 방문하지 않은 이웃 노드들을 큐에 넣으려고 하는데 check[9]는 true입니다. 그래서 큐에 아무것도 push하지 않고 9번 노드를 큐에서 pop만 해줍니다.
그리고 같은 방법으로 큐가 빌 때까지 탐색해주면 너비 우선 탐색(BFS)한 결과를 구할 수 있습니다.

---

BFS 실행했을 때 방문한 정점을 순서대로 출력하는 코드를 작성해 보았습니다. STL queue 컨테이너를 이용하여 구현하였으며 입력은 정점의 수(N), 간선의 수(M), 탐색 시작하는 정점 번호(V)를 순서대로 입력받고 M개 줄 만큼 간선의 양 끝점(u v)을 입력받습니다. 
백준 문제 (DFS와 BFS;1260)(https://www.acmicpc.net/problem/1260) 문제와 같은 입출력을 가집니다. 문제에서는 DFS 뿐만 아니라 BFS결과도 같이 출력해야 하지만 DFS도 같이 공부 한 뒤 둘 다 알았을 때 한 번 풀어보시는 걸 추천합니다.

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/tip/%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89.cpp

실행결과