문제 설명
•
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 문제
◦
1초 후에 X + 1, X - 1로 이동 가능
◦
0초 후에 2 * X로 이동 가능
예제 입력/출력
•
입력1
5 17
Plain Text
복사
•
출력1
2
Plain Text
복사
제약 조건
•
0 ≤ N ≤ 100,000
◦
: 수빈이의 위치
•
0 ≤ K ≤ 100,000
◦
: 동생의 위치
문제 풀이
•
BOJ 1697 숨바꼭질 응용 문제◦
이번 문제에서는 가중치의 값이 다르므로, BFS로 최단 거리를 구할 수 없다.
•
다익스트라 알고리즘을 이용하여 문제를 해결하면 된다. -
◦
모든 간선의 가중치가 0 이상(0과 1)이므로 다익스트라 알고리즘 사용 가능
풀이 코드
from queue import PriorityQueue
INF = int(1e12)
MAX = int(1e5)
# Input
N, K = map(int, input().split())
# Solve (다익스트라)
pq = PriorityQueue()
pq.put((0, N)) # (시간, 노드)
times = [INF for _ in range(MAX + 1)]
times[N] = 0
while not pq.empty():
cur_time, cur_node = pq.get()
nexts = [
(cur_node - 1, cur_time + 1),
(cur_node + 1, cur_time + 1),
(cur_node * 2, cur_time)
]
for next_node, next_time in nexts:
if 0 <= next_node <= MAX:
if next_time < times[next_node]:
pq.put((next_time, next_node))
times[next_node] = next_time
print(times[K])
Python
복사