[자료구조 및 알고리즘] 0-1 너비우선탐색 (0-1 BFS)

0-1 BFS

 

0-1 bfs는 가중치가 0과 1만 있는 최단 경로 문제를 말한다. 시간복잡도는 O(V+E) (V는 노드, E는 간선)으로, 조건을 만족하는 경우 다익스트라 알고리즘보다 더 효율적으로 작동한다. 일반적인 BFS 탐색과 동일하지만, 가중치가 0인 정점이 존재하기 때문에 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 한다. 즉, 결과 값이 방문 횟수의 최소가 아닌 가중치가 최소인 경우를 찾기 때문에 가중치가 낮은 경로부터 탐색해야 한다.

 

0-1 BFS 동작

 

1. 덱의 front에서 현재 노드를 꺼낸다.

 

2. 연결된 인접 노드를 살펴본다.

 

3. 현재까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다.

 

4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.

 

5. 덱에서 더 이상 꺼낸 노드가 없을 때까지 이 과정을 반복한다.

 

백준의 숨바꼭질 3문제가 이를 연습하기 좋은 문제이다.

 

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

13549번: 숨바꼭질 3