[백준] 13549 숨바꼭질

문제링크 : https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

import heapq
n, k = map(int, input().split())
INF = int(1e9)
dis = [INF] * 100001

def dikjstra(n):
    q = []
    heapq.heappush(q, [0, n])
    dis[n] = 0

    while q:
        time, now = heapq.heappop(q)

        if now == k:
            return dis[now]

        for next in (now*2, now-1, now+1):
            if 0<= next < 100001:
                if next == now*2:
                    if time < dis[next]:
                        dis[next] = time
                        heapq.heappush(q, [time, next])
                else:
                    temp = time + 1
                    if temp < dis[next]:
                        dis[next] = temp
                        heapq.heappush(q, [temp, next])

print(dikjstra(n))

 

오답노트

: 처음에는 숨바꼭질1을 풀듯이 bfs로 풀었다가 시간초과가 나서 고민을 하다, 다익스트라를 활용해야함을 알게되었다.

이후 temp를 사용하지않고 time +=1 했다가 다음 For문에서 time이 누적된 채 돌아가서 오답을 뱉어내 가벼운 디버깅 과정을 통해 잘못된 부분을 찾았다. 위치 이동 문제에서 그래프 범위안에 있는지 확인해주는걸 잊지말자!