백준 13549 숨바꼭질 3

과정

• 다익스트라 또는 BFS
• 최단시간으로 가는 경우를 찾기

import heapq

S, E = map(int, input().split())

INF = 1e9
dp = [INF] * 100001


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dp[start] = 0

    while q:
        time, now = heapq.heappop(q)
        if dp[now] < time:
            continue
        if now == E: # 도착지면 다시 실행할 필요 없음.
            continue

        if classification(now + 1):
            if dp[now + 1] > time + 1:
                dp[now + 1] = time + 1
                heapq.heappush(q, (time + 1, now + 1))

        if classification(now - 1):
            if dp[now - 1] > time + 1:
                dp[now - 1] = time + 1
                heapq.heappush(q, (time + 1, now - 1))

        if classification(now * 2):
            if dp[now * 2] > time:
                dp[now * 2] = time
                heapq.heappush(q, (time, now * 2))


def classification(index):
    if index < 0 or index > 100000:
        return False
    return True  # 계속 진행해도 됨

dijkstra(S)
print(dp[E])