[Algorithm] BFS / 0–1 BFS
- BFS 란? (아시는 분들 스킵가능)
- BFS(Breadth First Search) 란 그래프 탐색의 기법으로, 루트 노드로 부터 같은 레벨의 노드들 먼저 탐색하는 기법이다.
breadth 자체가 ‘폭’을 의미하며 그림과 같이 중심점에서 가까운, 같은 폭 먼저 물결이 일듯이 같은 레벨부터 탐색하고 다음 레벨로 넘어간다고 생각하면 된다. 물결은 1이 먼저, 그 다음에 2, 3, … 순차적으로 원을 그리며 일게 된다. 중심 점에서 가까운 폭 먼저 탐색 하므로 찾은 결과는 중심으로부터 최단거리를 보장한다.
- 탐색까지의 시간 복잡도는 모든 노드(V) 모든 간선(E) 를 고려하므로 O(E+V)가 된다. 주로 알고리즘 문제에서 최단거리를 구할 때 쓰인다.
2. 0–1 BFS 란?
- 가중치가 0과 1로 이루어진 Weighted Graph에서 실행되는 BFS로써, 결과 값은 최단거리가 아닌 Weight의 총 합이 가장 짧은거리를 구하게 된다.
- 네비게이션을 예로 들어보자. 도로의 종류는통행료가 1이 있는 구간과 통행료가 없는 구간으로 이루어져있을 때, 일반 BFS는 출발점 A 와 B 사이의 거리가 가장 짧은 경로를 나타난다고 하면, 0–1 BFS는 A와 B 사이의 거리 중 통행료의 총 합을 최소로 하는 최단거리를 구할 것 이다. 다음 예제를 통해 BFS와 0–1 BFS를 살펴보자.
- BFS
다음과 같은 길이 있다면 (길의 길이는 같다면) 서울 — 부산 까지 가는 최단거리를 BFS로 구해보자.
먼저 서울에서 가장 가까운 거리인 천안, 수원 먼저 탐색한다. 탐색한 도시에 부산이 없으므로 그 다음 단계를 탐색한다. 현재 탐색중인 각 도시(천안 수원)에서 거리 1인 도시를 또 탐색한다.
천안에서 한칸 씩 더 가면 대구, 수원이 후보 도시이지만 수원은 이미 1단계에서 탐색했으므로 빼고 대구를 추가해준다. 마찬가지로 수원으로부터 청주를 추가해준다. 여전히 부산이 없으므로 다음 단계도 탐색해준다.
3단계에서는 대구로부터 부산, 청주로부터 여수가 탐색지가 되었다. 이 탐색지에 부산이 있으므로 해를 찾았고, 최단거리는 3단계에서 발견했으므로 서울 — 부산 최단거리는 3이다.
- 0–1 BFS
1단계에선 먼저 거리에 상관없이 0원으로 갈 수 있는 도시를 찾는다.
2단계에선 1원으로 갈 수 있는 도시를 찾는다.
3단계에선 2원으로 갈 수 있는 도시를 찾는다. 부산을 찾았으므로 최소 비용으로 부산까지 가는 방법은 총 2원을 사용해 가는 것 이다.
3. 구현하기
- Deque
데크(Deque)란 Double Ended Queue로써 양 방향에서 pop 과 push 가 가능한 큐 이다. 일반적으로 BFS는 FIFO 자료구조인 일반 Queue를 사용해서 구현이 가능하지만 0–1 BFS는 Deque가 필요하다.
- 0–1 BFS
원리는 간단하다. 일반 BFS에서 Queue를 이용해서 같은 레벨의 노드들을 먼저 담고 탐색한 후 그 다음 레벨의 노드들을 담기 때문에 자연히 나중 레벨의 노드들은 이전 레벨의 노드들 보다 늦게 탐색하게 된다.
0–1 BFS에서는 가중치가 0인 경우 Deque의 왼쪽에 담고 1인 경우는 Deque의 오른쪽에 담기 때문에 가중치가 0인 것들 먼저 처리되고, 그 다음에 1인 것들이 처리, 그 다음에 2인 것들이 처리… 가 되게 되서 같은 가중치를 같은 Breadth(폭)으로 보고 BFS가 되는 것이고 찾은 노드의 결과는 가중치의 합이 최소가 되게 된다.
- root 노드에서 갈 수 있는 노드들을 Deque에 넣는다.
1) 만약 가중치가 0 이었다면 Deque의 왼쪽 입구에 넣는다.
2) 만약 가중치가 1 이었다면 Deque의 오른쪽 입구에 넣는다.
2. Deque의 왼쪽부터 pop해서 위의 1번을 반복한다.
3. 원하는 노드가 나올 때 까지 반복한다.