JIN_YOUNG _KIM
2023. 6. 20. 05:12
특징
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
