[백준/Python] #13549 숨바꼭질 3

문제

 

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

13549번: 숨바꼭질 3

---

Algorithm

문제의 상황을 그래프로 나타내고 다익스트라로 해결할 수 있다. 생성해야 할 그래프는 왼쪽으로, 또는 오른쪽으로 갈 수 있으면 현재 점 i에서 i-1 또는 i+1인 노드로 이동하며 이 때의 비용은 각 1이고, 순간이동이 가능하다면 i에서 2*i노드로 이동하며 비용은 0인 그래프이다. 이 때 노드의 개수는 N 또는 K의 범위의 길이이다.

---

 

 

Code

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

MAX = 100000

N, K = map(int, input().split())

graph = [[] for _ in range(MAX + 1)]
for i in range(MAX + 1):
    if i > 0:
        graph[i].append((i - 1, 1))
    if i < MAX:
        graph[i].append((i + 1, 1))
    if 2 * i <= MAX:
        graph[i].append((2 * i, 0))

def dijkstra(dept, dest):
    q = []
    T = [float("inf") for _ in range(MAX + 1)]

    T[dept] = 0
    heappush(q, (dept, 0))

    while q:
        loc, t = heappop(q)
        if T[loc] < t:
            continue
        for nl, w in graph[loc]:
            w += t
            if T[nl] > w:
                T[nl] = w
                heappush(q, (nl, w))

    return T[dest]

print(dijkstra(N, K))