백준 13549번 숨바꼭질 3

문제 풀이

• 본 문제는 다익스트라 알고리즘을 이용하면 문제를 해결할 수 있습니다.
• 그래프 문제에서 시작 노드에서 도착 노드가 이어져 있다는 것을 응용해서 해당 문제는 특정 칸에서 갈 수 있는 경우의 수를 3가지(+1, -1, X2)로 보면 됩니다.

코드 풀이

import sys, heapq
input = sys.stdin.readline

N, K = map(int, input().split())
INF = int(1e9)
dist = [INF] * 100001


def dijkstra(start):
    q = []
    heapq.heappush(q, [0, start])
    dist[start] = 0
    while q:
        distance, now = heapq.heappop(q)
        dx = [-1, 1, now]   # 현재 칸에서 갈 수 있는 경우의 수는 +1, -1, X2
        move = [1, 1, 0]   # 이동할 때 비용은 +1: 1, -1: 1, X2: 0
        # 현재까지 알려진 최소 비용이 더 작다면 반복 스킵
        if dist[now] < distance:
            continue
            
        # 현재 칸에서 갈 수 있는 경우(now + dx[i])는 3가지
        for i in range(3):
        	# 칸의 범위(0 <= X <= 100,000)을 벗어나면 for문 스킵
            if now+dx[i] > 100000 or now+dx[i] < 0:
                continue
            # 현재 칸(distance)에서 다음 칸(i)으로 갈 때의 비용(cost)
            cost = distance + move[i]
            if cost < dist[now+dx[i]]:
                dist[now+dx[i]] = cost
                heapq.heappush(q, [cost, now+dx[i]])


dijkstra(N)
print(dist[K])