[백준] 13549. 숨바꼭질3/Python - Gold5

❓문제

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

성능 요약

메모리: 115084 KB, 시간: 232 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 데이크스트라, 0-1 너비 우선 탐색

 

문제 설명

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

✍🏻풀이

거리를 전부 INF로 초기화한 후 시작점만 0으로 초기화한다. 그리고 힙 큐에 시작 위치 N과 현재 시간 0을 기록한다.

이 경우에는 정점의 개수가 정해져 있는 것이 아니므로 힙 큐 안에 원소가 존재하는지 안 하는지 여부로 while문을 실행한다.
다음 위치가 0 에서 100,000 사이이면서 더 적게 걸리는 시간을 다음 위치에 기록한다. 그리고 다음 위치와 시간을 힙 큐에 넣는다.
이렇게 하면 힙 큐에 원소가 있을 때까지 확인하고 힙 큐가 비어있다면 이제 동생을 찾을 수 있는 가장 빠른 시간을 출력하면 된다.

💻코드

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
INF = 1e9
N, K = map(int, input().split())
time = [INF] * 100001

def dijkstra():
    time[N] = 0
    move = []
    heappush(move, (0, N))

    while move:
        t, x = heappop(move)
        for nt, nx in [(t, x*2), (t+1, x+1), (t+1, x-1)]:
            if 0 <= nx <= 100000 and time[nx] > nt:
                time[nx] = nt
                heappush(move, (nt, nx))

dijkstra()
print(time[K])

📍후기

계속 런타임 에러가 나서 왜 그런가 했는데 heapq가 먼저 소진되는 경우와 x 범위가 벗어나는 걸 고려하지 않아서 에러가 났다...그래서 중간에 BFS로 바꿔봤는데 난 아무리 해도 안 돼서 결국 다시 heapq로 성공...