알고리즘 : 너비 우선 탐색(BFS)

 

우선 그래프, 트리, 큐 자료구조에 대해 모르고 있다면 아래의 포스팅을 우선 확인하는 것이 좋다.

 

자료구조 그래프 (graph)

 

자료구조 트리 (tree)

 

자료구조 큐 (queue)

 

 

 

너비 우선 탐색 (BFS : breadth first search)는 어떠한 자료구조를 대상으로 특정한 값을 찾거나, 전체를 탐색하기 위한 알고리즘 중 하나이다.

 

BFS 를 이용한 미로찾기 예시

 

이때 어떠한 자료구조는 한 방향이 아니라 여러 방향으로의 탐색을 지원해야 한다. 즉 일반적인 연결리스트, 스택, 큐 등의 자료구조를 대상으로는 BFS를 사용할 수 없다.

 

반대로 그래프, 트리등의 다차원 자료구조와, 배열, 벡터 등의 랜덤 액세스를 지원하는 자료구조 등 탐색 방향을 여러 개 정의할 수 있는 자료구조에서는 모두 사용 가능하다.

 

아래의 예시는 1차원 배열에서, 탐색방향을 3개 (+1, -1, *4 방향 탐색)로 하여 너비 우선 탐색을 한 예시이다.

심지어 1차원 배열도 BFS 가능

 

---

 

BFS는 여러 개의 탐색 가능한 대상이 존재할때 (= 여러 개의 이동 가능 경로가 존재할 때), 그 대상들을 '순서대로' 탐색한다. 

 

예를 들어 아래와 같은 그래프가 있다고 가정하자, 1번 노드부터 BFS를 하려 한다.

 

 

1번 노드에서 이동 가능한 경로는 2개 (= 탐색 가능한 대상은 2번, 3번 노드)이다.

 

 

 

 

이후 2번 노드를 탐색했다고 가정하자. 그러면 추가로 4번 노드가 탐색 가능한 노드로 추가된다

 

 

 

이다음 탐색 노드를 결정할 때 BFS의 탐색 규칙이 작동한다. 

3번 노드와 4번 노드 중 3번 노드가 먼저 탐색 가능한 노드로 추가되었다.

그러므로 순서상 3번 노드를 탐색하는 것으로 결정된다.

 

 

 

 

 

이러한 방식으로 탐색을 반복해 나가는 것이 너비 우선 탐색, BFS이다.

 

---

탐색 가능한 지점을 '순서대로' 탐색할 것 이기 때문에 BFS의 구현에는 큐를 이용하기 좋다.

새롭게 탐색 가능한 지점이 추가될 때마다 큐에 넣어주고. 실제 탐색은 큐에서 값을 하나 빼서 탐색을 진행할 경우 BFS의 룰을 그대로 따르게 되기 때문이다.

 

---

BFS를 이용하기 좋은 예시는 BFS의 친구라고 볼 수 있는 DFS에 대한 포스팅 이후, BFS vs DFS 포스팅에서 다루는 것이 맞다고 생각된다. (DFS와 장단점이 반대이기 때문에 비교하기 좋다)

 

우선은 BFS가 무엇인지, 어떤 특징이 있는지, 구현은 어떤 방식으로 되는지를 포스팅해 보았다.