특징
1. 가중치가 0과 1로만 이루어 져 있을 때에만 사용이 가능
2. 일반적인 큐가 아닌 데큐(Deque)를 사용해야 한다.
알고리즘의 핵심 포인트
1. 가중치 그래프이므로, 기존의 BFS로 최단 경로를 구할 때와 같이 [깊이]가 아닌, [가중치의 최소합]이 최단 경로의 길이가 된다.
2. 위 1의 [가중치의 최소합]을 구하기 위하여,
a) 가중치의 합이 0인 경로...
b) 가중치의 합이 1인 경로..
c) 가중치의 합이 2인 경로..
-> 가중치의 합이 0인 경로부터 시작하여 , +1씩하여 1인 경로를 탐색한다.
3. 데큐(Deque)로부터 removeFirst()를 한 노드가 target 노드이면 알고리즘 종료!
아래의 문제를 기준으로, 그림을 그려보았다.
https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
www.acmicpc.net
'알고리즘(アルゴリズム） > 자주 까먹는 알고리즘(よく忘れるアルゴリズム）' 카테고리의 다른 글
| 벨만-포드 알고리즘(가중치가 음수일 때의 최단경로) (0) | 2023.06.23 |
|---|---|
| 플로이드 - 워샬 알고리즘 (0) | 2023.06.23 |
| 다익스트라 알고리즘 (0) | 2023.06.15 |
| 이진수를 이용하여 O(log n)으로 거듭 제곱 빠르게 계산하기 (2) | 2023.01.30 |
| 조합론(Combination) == 이항 계수(binomial Coefficient) (0) | 2023.01.29 |