Computer Science/Algorithm
[Algorithm] 0-1 BFS
0-1 BFS란? BFS를 기반으로 가중치가 0,1로 주어진 그래프에서 최단경로를 찾아낼 수 있는 알고리즘이다. 기본적으로 그래프에 대한 이해와 최단경로 다익스트라 알고리즘에 대한 이해가 필요하다. 최단경로 알고리즘에는 다익스트라 알고리즘을 사용할 수 있지만, 시간복잡도가 O(ElogE) 또는 (ElogV)인 반면에 0-1 BFS는 O(V+E)의 시간 복잡도로 문제를 해결할 수 있다. 가중치 0인 정점이 존재하기 때문에, 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야한다. 그렇기 때문에 결과 값이 방문 횟수의 최소가 아닌 가중치의 최소인 경우를 찾기 위해서는 가중치가 낮은 경로부터 탐색해야한다. 가중치가 낮은 정점으로의 이동을 높은 우선 순위로 해야하기 때문에, 덱의 가장 앞단..
