해당 문제는 두 가지의 방법으로 풀 수 있었고, 그 중에서 처음 적용하는 응용 알고리즘을 배웠다.
그래프에서 간선의 가중치가 0 또는 1밖에 존재하지 않을때 이용할 수 있는 응용 BFS 기법이다.
보통 위와 같은 간선이 주어지면 가장 Naive한 방법은 Dijkstra를 이용하는 방법이다.
하지만 다익스트라의 시간복잡도는 O(ElogV+V)인 반면에 0-1 BFS를 이용하면 O(V + E)인 선형적인 복잡도 내에서 탐색을 종료할 수 있다.
0-1BFS의 원리의 핵심은 기존 BFS와 다르게 Deque를 이용하는것에 있다.
만약 우리가 특정 정점 u에 존재하고 인접 정점 v와 연결되는 간선 E(u, v)가 존재할때 두 가지의 상황이 존재함을 확신할 수 있다.
이렇게 확신할 수 있는 이유는 모든 간선의 가중치가 0 또는 1이기 때문이다.
따라서 다익스트라처럼 큐에는 오직 이진 정점을 통해 최단 거리가 줄어든 정점만 큐에 삽입한다.
만약 v정점이 u와 같은 레벨이라면 큐의 앞부분에 삽입하고, 아니라면(1차이) 큐의 뒷 부분에 삽입한다. 이것은 BFS의 작동을 위해 큐가 정렬된 상태를 유지한다.
일반적인 큐의 구조에선 O(1)안에 위의 과정을 수행하지 못하기에 덱 자료구조를 이용한다.
일반적인 다익스트라 방식으로 풀 수 있다. dist배열의 가중치를 더할때 x * 2 부분은 기존 currentNode의 가중치와 동일하게 가져가게 되면 최소 경로값을 알아서 찾아가므로 Naive하게 풀 수 있다.