[Python] 백준 13549번 숨바꼭질

문제

13549번: 숨바꼭질 3

입력

• 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

• 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

입력 예제

5 17

출력 예제

2

문제 풀이

• 수빈이가 있는 곳에서 순간이동 가능한 모든 거리까지 도달하는데 걸리는 시간을 탐색한 후, 동생이 있는 곳의 좌표 값을 리턴
• 순간이동 할 때 (x + 1), (x - 1)의 값은 1이고, (x * 2)의 값은 0이므로, 이동좌표를 탐색할 때 시간 값도 넣어서 같이 탐색할 수 있도록 한다.

 

코드

import heapq
import sys
INF = int(1e9)
input = sys.stdin.readline
n, m = map(int,input().split())
distance = [INF] * 100001


def dijkstra(start, end):
    q = []
    # 비용, 노드순으로 힙에 넣기
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        # 꺼낸 시간이 더 오래 걸린다면 무시
        if distance[now] < dist:
            continue

        # 꺼낸 시간이 더 적게 걸리면 순간이동 (*2의 거리비용 0)
        for i in [(now - 1, 1), (now + 1, 1), (now * 2, 0)]:
            # 이동한 곳의 좌표가 범위 벗어나는 경우 무시
            if i[0] < 0 or i[0] >= 100001:
                continue
            # 좌표 넘어가지 않는다면 i[0]까지 도달할 수 있는 최소시간 탐색
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    # 목적지까지 도달하는데 걸린 시간 리턴
    return distance[end]

print(dijkstra(n, m))