코딩테스트 복기 - 최단거리를 가장 빠르게 구할 수 있는 0-1 BFS 알고리즘
1. 문제 그래프 G가 V개의 정점과 E개의 간선으로 이루어지며 간선의 가중치가 0 또는 1이다. 이때 두 정점 사이의 최단 경로를 찾는 효율적인 코드를 작성해야한다면? 2. 다익스트라 알고리즘이 항상 정답인가? 많은 경우에 다익스트라 알고리즘을 선택하지만, O(E+VlogV)가 최상의 구현이지만, 최악의 경우 효과적이지 않다. 많은 사람들이 이 문제를 보면 다익스트라 알고리즘을 선택하고, 효율적이지 않을때, 최적화할려고 노력하지만, 다익스트라 알고리즘이 최상이라고 생각한다면.. 매우 간단하면서 BFS를 이용한 아주 아름다운 0-1 BFS라는 기법을 알 필요가 있다 보조정리(Lemma) : "BFS 수행중에 정점을 포함하는 큐는, BFS 트리의 최대 2개의 연속한 레벨의 원소만을 포함할 수 있다" Lem..
