문제 링크

유사 문제: DSLR

풀이

숨바꼭질2 와 다른점은 순간이동시에 시간소요 여부이다.

숨바꼭질2는 모든 간선의 가중치가 1로 동일했지만 숨바꼭질3은 도보이동시 1, 순간이동시 0으로 가중치가 다르다.

따라서, BFS가 아닌 다익스트라로 푸는 것이 효율적이다.

코드

import heapq
from collections import defaultdict
INF = int(1e9)
MAX = 100000

def dijkstra(graph,start):
    distance = [INF]*(MAX+1)
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
    return distance

if __name__ == '__main__':
    N,K = map(int,input().split())
    graph = defaultdict(list)
    for i in range(MAX+1):
        for nxt in [i+1,i-1]:
            if nxt not in graph[i] and 0<=nxt<=MAX:
                graph[i].append((nxt,1))
        if 2*i not in graph[i] and 0<=2*i<=MAX:
            graph[i].append((2*i,0))
    print(dijkstra(graph,N)[K])