[백준 알고리즘] 13549. 숨바꼭질 3

 

 

 

처음에는 BFS로 풀려고 했으나 순간이동은 시간을 세지 않는 다는 점에서 최단 시간을 확정하기 어렵다는 생각이 들었다. 그래서 다익스트라로 접근했다.

 

 

from collections import deque

def find_K():
    D = [0xfffffffffff] * 100001
    D[N] = 0
    Q = deque()
    Q.append((0, N))
    while Q:
        time, loc = Q.popleft()
        if D[K] <= time: continue
        for n_time, n_loc in [(time+1, loc+1), (time+1, loc-1), (time, loc*2)]:
            if 0 > n_loc or 100000 < n_loc: continue
            if D[n_loc] > n_time:
                D[n_loc] = n_time
                Q.append((n_time, n_loc))

    return D[K]


N, K = map(int, input().split()) # 수빈, 동생
# 순간이동은 0초 , +1, -1 은 1초
print(find_K())