BOJ 13549 숨바꼭질 3 Python3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

 

 

※ BFS로 풀면 메모리 초과 나서, 또익스트라로 풂

 

 

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)
N, K = map(int, input().rstrip().split())
distance = [INF]*100001

def hide_and_seek():
    queue = []
    heapq.heappush(queue, (0, N))
    while queue:
        weight, now = heapq.heappop(queue)
        if now == K:
            distance[now] = weight
            return
        if distance[now] < weight:
            continue

        next_now = now - 1
        cost = weight + 1
        if (next_now >= 0) and (distance[next_now] > cost):
            distance[next_now] = cost
            heapq.heappush(queue, (cost, next_now))

        next_now = now + 1
        cost = weight + 1
        if (next_now <= 100000) and (distance[next_now] > cost):
            distance[next_now] = cost
            heapq.heappush(queue, (cost, next_now))

        next_now = now * 2
        cost = weight
        if (0 <= next_now <= 100000) and (distance[next_now] > cost):
            distance[next_now] = cost
            heapq.heappush(queue, (cost, next_now))

hide_and_seek()
print(distance[K])