0-1 BFS 알고리즘
1. 0-1 BFS란?
0-1 BFS는 가중치가 0,1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘이다. 최단경로 알고리즘에는 다익스트라 알고리즘을 사용할 수 있지만, 시간 복잡도가 $O(Elog{E})$ 또는 $O(Elog{V})$인 반면에 0-1 BFS는 $O(V+E)$의 시간 복잡도로 문제를 해결할 수 있다.
일반적인 BFS 탐색과 동일하지만, 가중치가 0인 정점이 존재하기 때문에 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 한다. 그렇기 때문에 결과 값이 방문 횟수가 최소가 아닌 가중치의 최소인 경우를 찾기 위해서는 가중치가 낮은 경로부터 탐색해야 한다.
정점 1에서 정점 2로의 이동 = 방문 횟수 1, 가중치 1
정점 1에서 정점 3,4를 거쳐 정점 2로의 이동 = 방문 횟수 3. 가중치 0
가중치가 낮은 정점으로의 이동을 높은 우선 순위로 해야하기 때문에 덱의 가장 앞단(front)에 삽입한다. BFS와 동일하게 간선의 갯수(E)만큼 탐색을 하게되고, 정점의 개수(V)만큼 중복없이 방문하기 때문에 시간 복잡도는 $O(V+E)$로 동일한다.
2. 0-1 BFS의 동작
왜 0-1 BFS가 $O(V+E)$에 동작할 수 있을까? 이는 BFS에서 노드를 관리하기 위해 큐를 사용하는 대신 덱(deque)을 사용하여 실현할 수 있다.
0-1 BFS는 다음 과정을 따라 최단 경로를 찾게 된다.
- 덱의 front에서 현재 노드를 꺼낸다.
- 연결된 인접 노드를 살펴본다.
- (현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용) 이면 소비된 비용을 갱신해준다.
- 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 back에 삽입하도록 한다.
- 덱에서 더 이상 꺼낼 노드가 없을 때까지 위 과정을 반복한다.