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

기본 개념

---

'너비 우선 탐색'이란 그래프(혹은 트리와 같은 자료구조)를 탐색하는 방법 중 하나로, 자신이 탐색할 수 있는 가장 가까운 곳을 우선적으로 탐색하는 알고리즘이다. 다시 말해, 루트 노드에서부터 시작해 인접한 자식 노드들을 한 번씩 탐색하고 이를 반복해 탐색을 수행하는 알고리즘이다.

 

자신과 가까운 모든 경로를 탐색하고 그다음 거리의 경로를 탐색한다. 때문에 모든 경로를 탐색해야 하는 경우 '깊이 우선 탐색'보다 빠르게 수행할 수 있다는 장점이 있다.

 

 

 

예시

---

3*3, 총 9칸의 보드가 있고 이 보드를 탐색한다고 해보자. (움직일 수 있는 방향은 상하좌우 네 방향뿐이며 현재 내 위치는 A이다.) 너비 우선 탐색에서는 Queue를 이용해 탐색하는 방식을 주로 사용한다. Queue를 만들어주고 내 위치를 넣어준다. 이제 이 Queue에서 값을 하나씩 꺼내고 그 값에서 가장 가까운 위치를 다시 Queue에 넣는 것을 반복해 탐색하면 된다. 

 

Queue에서 가장 먼저 들어온 값 A를 꺼내 준다. A와 근접한 위치는 어디인가? A의 우측과 아래에 존재하는 B와 C다. B와 C를  순서대로 Queue 속에 넣어주겠다.

 

다들 알다시피 Queue는 FIFO 방식이다. 그렇다면 이번에는 Queue에서 B가 꺼내져 나올 것이다. B에서 탐색해보자. B와 한 칸 차이나는 곳은 A, E, D다. 하지만 A는 이미 한번 탐색한 곳이다. 다시 한번 탐색할 필요가 없다. D와 E를 순서대로 탐색했으니 순서대로 Queue에 넣어준다.

 

이번에는 C가 나올 차례다. C와 근접한 곳은 A, E, F다. 그러나 A와 E는 이미 한 번씩 탐색한 곳이다. 그렇다면 C는 두 곳을 탐색할 필요가 없다. 두 부분을 넘어가고 F를 탐색하고 Queue에 넣어준다.

 

이제 감이 좀 잡혔을 것이라 생각한다. 같은 방식으로 이를 이어가면 된다. 반복되기 때문에 설명을 줄이고 과정을 한번 빠르게 보도록 하자.

위의 설명을 잘 따라왔다면 어떤 방식으로 탐색이 반복되었는지 쉽게 파악할 수 있을 것이다. Queue가 완전 빌 때까지 반복문을 돌리면 루트 노드와 연결되어 있는 모든 노드들을 근접 노드를 우선적으로 모두 탐색할 수 있다. 위의 예시의 경우 Queue가 비진 않았지만 모든 곳의 탐색을 끝냈다. 만일 목표한 것이 I까지 가는 것이었다면, Queue가 비어있지 않더라도 I를 탐색한 순간 반복을 멈추면 된다.

 

이와 같은 방식으로 Queue에 탐색한 위치를 넣고, 차례로 꺼내 근접한 곳을 탐색한다.  그리고 이를 반복한다. 이렇게 하면 다른 방식보다 효율적이고 빠르게 인접한 노드들을 탐색할 수 있게 된다. 이것이 너비 우선 탐색 알고리즘이다.

 

 

 

예시 문제

---

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색