[Python] 백준 13549번 숨바꼭질 3(dijkstra)

문제

풀이

규칙 중에 조금 헷갈린 부분이 있는데 2를 곱하여 워프 할 때는 비용이 발생하지 않는 것이다.

또한 동생보다 수빈이가 더 숫자가 높을 수도 있다.

이것만 주의하면 될 것 같다.

처음 이 문제를 보고 생각난 풀이 방법은 동적 계획법 이다. 점화식을 이렇게 세울 수 있을 것 같기 때문이다.

도착지를 x라 하였을 때, arr[x]=min(arr[x]//2, arr[x-1]+1,arr[x+1]+1)

이렇게 해서 데이터를 쌓아 가면 풀 수 있을 거라 생각 했으나... 뒤 또는 앞으로 갈 수 있다는 방식 때문에 top down, bottom up 둘 중 무엇도 사용하지 못한다는 문제가 있어서 이 풀이는 포기 하였다.

두 번째로 생각한 것은 bfs였다. bfs로 앞으로 한 칸, 뒤로 한 칸, 두 배로 칸 뛰기를 모두 탐색하여 목표 지점 까지 최소 거리를 구하는 것이다.

하지만 다익스트라 문제 연습을 하기 위해서 다익스트라로 풀었다.

bfs와는 다른 점은 다익스트라는 우선순위 큐를 사용하여 항상 최소의 거리 먼저 탐색하기 때문에 경우의 수가 bfs 보다는 줄어들 것 이다.(아마?)

결과적으로는 bfs에서 큐를 우선순위 큐로 바꾼 것에 지나지 않는다.

import sys

import heapq

input = sys.stdin.readline

INF = int(1e9)

start, k = map(int, input().split())

distance = [INF]*(100001)

def dijkstra(start):

    q = []

    move = [1, -1]

    heapq.heappush(q, (0, start))

    distance[start] = 0

    while q:

        dist, now = heapq.heappop(q)

        cost = dist + 1

        if distance[now] < dist:

            continue

        for i in move:

            if now+i >= len(distance) or now+i < 0:

                continue

            if cost < distance[now+i]:

                distance[now+i] = cost

                heapq.heappush(q, (cost, now+i))

        if now*2 < len(distance) and dist < distance[now*2]:

            distance[now*2] = dist

            heapq.heappush(q, (dist, now*2))

    return

if start == k:

    print(0)

    exit(0)

dijkstra(start)

print(distance[k])