난이도 : 골드 5
유형 : 최단경로
https://www.acmicpc.net/problem/13549

---

문제 접근

• 수빈이의 위치 N, 동생의 위치 K (0 ≤ N, K ≤ 100,000)
• 가능한 이동 방법:
  • X - 1 (1초 소요)
  • X + 1 (1초 소요)
  • X * 2 (0초 소요)
• 가장 빠르게 동생에게 도달하는 시간을 출력해야 한다.

핵심 아이디어

이 문제는 다익스트라 알고리즘을 통해 풀 수 있다.

조건	만족함?	설명
그래프 구조인가?	✅	위치들을 노드, 이동을 간선으로 생각 가능
가중치가 있는가?	✅	순간이동(0), 걷기(1)
가중치가 음수가 아닌가?	✅	0 또는 1만 존재
최단 시간(거리)를 구하는 문제인가?	✅	N → K까지 가장 빠른 시간 구하기

위치 0 ~ 100000까지가 각각 노드
노드에서 노드로 이동할 수 있는 방법은:
X → X-1 (1초)
X → X+1 (1초)
X → X×2 (0초)

이건 가중치가 있는 방향 그래프인데,
이 문제에서 가중치는 거리가 아니라 시간이다.
그렇기에 우선순위 큐에 (시간,위치) 의 튜플 꼴로 넣어서 푼다.

해답 및 풀이

import heapq

def dijkstra(n, k):
    MAX = 100001
    min_time = [float('inf')] * MAX  # 각 위치까지의 최소 시간
    min_time[n] = 0  # 시작점은 0초에 도착

    heap = []
    heapq.heappush(heap, (0, n))  # (걸린 시간, 현재 위치)

    while heap:
        current_time, current_pos = heapq.heappop(heap)

        # 이미 더 빠른 시간으로 방문한 적이 있으면 무시
        if min_time[current_pos] < current_time:
            continue

        # 1. 순간이동 (가중치 0)
        next_pos = current_pos * 2
        if next_pos < MAX and current_time < min_time[next_pos]:
            min_time[next_pos] = current_time
            heapq.heappush(heap, (current_time, next_pos))

        # 2. 앞으로 이동 (가중치 1)
        next_pos = current_pos + 1
        if next_pos < MAX and current_time + 1 < min_time[next_pos]:
            min_time[next_pos] = current_time + 1
            heapq.heappush(heap, (current_time + 1, next_pos))

        # 3. 뒤로 이동 (가중치 1)
        next_pos = current_pos - 1
        if next_pos >= 0 and current_time + 1 < min_time[next_pos]:
            min_time[next_pos] = current_time + 1
            heapq.heappush(heap, (current_time + 1, next_pos))

    return min_time[k]

간선이 꼭 거리가 아니고 시간이 될 수 도 있음을 배웠다.
BFS로 풀면 더 수월할 것 같았지만 유형이 다익스트라 학습이기 때문에 다익스트라로 풀었다.