가중치(비용)이 0 과 1만 있을 떄 최단거리 구하기
비용이 0 과 1로 나뉘어져 있을 때 다익스트라 알고리즘을 deque로 사용할 수 있다
매 노드를 탐색할 떄 마다 갈 수 있는 노드에 대한 비용이 0이면 앞에, 1이면 뒤에 추가
하면서 탐색
다익스트라보다 빠른 속도
ex) 백준 1261번 알고스팟
'알고리즘' 카테고리의 다른 글
| 최소 스패닝 트리 (MST, Minimum Spanning Tree) (0) | 2022.03.03 |
|---|---|
| 배낭 문제 (Knapsack Problem) (0) | 2022.01.22 |
| 플로이드-워셜 ( Floyd-Warshall) (0) | 2022.01.19 |
| 다익스트라 최단경로 (Dijkstra) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 (Dynamic programming) (0) | 2022.01.19 |