다익스트라와 0-1 BFS에 대한 고찰

가중치가 존재하는 그래프 즉 0과 1 이 두 개만 존재하는 그래프가 존재한다고 했을 때 이때 다익스트라 알고리즘을 사용하면 O(ELogV)의 시간복잡도를 갖는다.

 

하지만 이런 상황에서는 우선순위 큐가 아닌 덱을 활용하여 O(E+V)의 시간복잡도로 해결할 수 있다. logV가 매우 강력한 복잡도이긴 하지만 역시 곱보단 합이 훨씬 시간적으로 이득이다.

 

그 방법또한 간단하다. 덱을 이용해서 다음에 넘어가려는 곳의 가중치가 1이라면 덱의 뒤쪽에 append 0이라면 앞에 append해주면 된다. append와 pop은 O(1)이고 V개의 정점에서 탐색하고 E개의 간선만큼의 값이 큐에 들어가므로 O(V+E)이다.

 

원리는 다음과 같다. 일단 탐색을 진행하면서 다음 노드가 0이라면 누적값에 0을 더하면 값이 변하지 않으므로 앞에 넣어주고 탐색을 계속 해준다. 만약 1이라면 뒤에 넣어주고 나중에 탐색한다.

 

이렇게 되면 비용 0으로 갈 수 있는 모든 노드를 탐색하고 그 다음에는 비용 1으로 갈 수 있는 모든 노드를 탐색하고 비용2로 시작할 노드들이 뒤에 들어간다.

 

결국 덱에는 0,....,0,1,1,...,1,1이나 1,1,...1,1,2,....2,2,2 그 다음은 2,2,2...,2,3,3,...,3,3 이런 식으로 채워지게 된다. 머리속으로 몇번 굴려보면 이해가 될 것이다.

 

즉 이런 경우에 위와 같은 알고리즘을 사용할 수 있고 그것이 0-1 BFS이다.

알고리즘 이름에는 BFS가 들어가는데 실제로 돌아가는 것은 다익스트라와 비슷하게 굴러가는 것 같다 ㅋㅋㅋㅋㅋㅋㅋㅋ