13549번 숨바꼭질 3 G5

숨바꼭질 시리즈 중 3번 문제

현재 점 N (0≤ N ≤ 100000)에서 K (0≤ K ≤ 100000)까지 도착하는 가장 빠른 시간을 구하는 문제

현 위치 X에서 X-1 또는 X+1로 걸어서 이동할 수 있고 이때는 1초가 걸린다.
2*X로 순간이동을 할 때는 0초가 걸린다.

숨바꼭질 시리즈 1, 2번은 단순 bfs로 해결 가능했다.
그런데 이 문제는 순간이동 시 걸리는 시간이 0초여서 다익스트라로 해결해야했다.

bfs로 해도 순서만 잘 맞추면 해결 가능하다고 하지만 나는 다익스트라를 열심히 공부했으니 써먹어야겠다.

정말 다익스트라 그 자체라서 따로 설명을 쓸게 없다.
큐에서 걸린 시간(cnt)이 가장 작은 것을 꺼내고 그 때의 위치(pos)로 visited를 확인했을 때(visited[pos]) 기록 되어있는 시간이 같다면(visited[pos] == cnt),

즉, 해당 위치에서의 최소 시간이 맞으면
그 위치에서 이동했을 때 (걷기 또는 순간이동) 범위 안에 있는지, 더 적은 시간이 걸리는지 확인하고 갱신해준다.

이런 과정이 끝났을 때 visited[k] 에 기록되어있는 값이 답이 된다.

from sys import stdin
import heapq

n, k = map(int, stdin.readline().split())
inf = float('inf')
visited = [inf for i in range(100001)]

q = []
heapq.heappush(q, (0, n))
visited[n] = 0

while q:
    cnt, pos = heapq.heappop(q)
    
    move = [(pos, 0), (-1, 1), (1, 1)]

    if visited[pos] == cnt:
        for go, sec in move:
            if 0<=pos+go<=100000 and visited[pos+go] > cnt + sec:
                visited[pos+go] = cnt+sec
                heapq.heappush(q, (cnt+sec, pos+go))

print(visited[k])