0-1 BFS 알고리즘

이번 포스팅에서는 0-1 BFS 알고리즘에 대해 알아보고자 한다.

 

백준 13549 숨바꼭질3 문제를 풀 때 0-1 BFS 알고리즘이 있다는 사실을 알게 되었다.

 

0-1 BFS는 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 푸는 것이다.

가중치가 0과 1만 있을 때는 최단거리를 찾을 경우에 다익스트라가 가장 좋은 선택이 아니다.

 

다익스트라 알고리즘의 시간 복잡도는 \(O(ElogE)\) 혹은 \(O(ElogV)\)인 반면, 0-1 BFS를 사용하면 \(O(V+E)\)의 상수시간으로 문제를 해결할 수 있다.

 

🍀 0-1 BFS의 동작 과정

deque를 활용해서 진행한다.

1. deque에서 popleft()로 현재 노드를 꺼낸다.
2. 연결된 인접 노드를 살펴본다.
3. 현재 노드까지의 값 + 다음 노드를 향하는 비용 < 다음 노드에 들어있는 값 이면 갱신해준다.
4. 노드가 갱신될 때, 다음 노드를 향하는 가중치가 0이면 deque의 앞(appendleft()), 1이면 deque의 뒤(append)에 삽입한다.
5. deque에서 더 이상 꺼낼 노드가 없을 때까지 반복한다.

비용이 적은 경로부터 탐색을 하게 되기 때문에 특정 간선을 2번 이상 지나가지 않는다. \(O(E)\)
모든 정점도 2번 이상 경유하는 경우가 없으므로 덱 크기는 최대 \(|V|\)이다 \(O(V)\)

따라서 0-1 BFS는 \(O(V)+O(E)=O(V+E)\)의 시간 복잡도를 가지게 된다.

 

---

참고사이트
https://nicotina04.tistory.com/168