[Algorithm] 0-1 BFS

0-1 BFS : 가중치가 0과 1만 있는 그래프에서 작동하는 알고리즘

 

0-1 bfs는 시간 복잡도 O(V+ E)로 다익스트라 알고리즘의 O(ElogE) 또는 O(VlogV) 보다 빠릅니다.

 

가중치가 0인 정점이 존재하기 때문에 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 합니다. 결괏값이 방문 횟수가 아니라 가중치의 최소를 구하는 문제에서는 가중치가 낮은 경로부터 찾아야 합니다.

 

 

0과 1의 가중치를 가진 그래프

정점 1에서 2로 이동 = 방문 횟수 1, 가중치 1

정점 1에서 3, 4를 거쳐 2로 이동 = 방문 횟수 4, 가중치 0

 

탐색을 할때 가중치가 낮은 노드를 먼저 돌아야 하므로 가중치가 낮은 노드는 큐의 앞(front)에 삽입합니다.

 

파이썬의 우선순위 큐에서는 리스트의 앞에 삽입하는 기능이 없으므로 deque(데크)를 사용하여 'appendleft() 함수'로 큐의 앞에 삽입한다.

 

https://hgk5722.tistory.com/168

[백준] 13549 파이썬(python) : 숨바꼭질 3 - 0-1 BFS