[백준/Python] #13549 숨바꼭질3

https://www.acmicpc.net/problem/13549

• Algorithm

점의 위치는 0~ 100000내에 존재하므로, 그래프를 생각했을 때 1~50000까지의 그래프 배열에는 2배를 한 위치로 이동할때 cost가 없고, 0~100000까지는 +1, -1칸 까지 이동할때는 cost가 1이 발생하도록 설정하여 다익스트라를 쓰면 된다고 생각했다.

위 사진처럼 그래프를 구성하였고, 시작점을 수빈이가 있는 위치로해서 distance배열계산을 하고, 동생의 위치를 출력해주면 된다.

• Code

import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
BOUND = 100000

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

INF = int(1e9)
graph = [[] * (BOUND+1) for _ in range(BOUND+1)]
distance = [INF] * (BOUND+1)

for i in range(BOUND+1):
    if i > 0:
        graph[i].append((i-1,1))
    if i < BOUND:
        graph[i].append((i + 1, 1))
    if i*2 > BOUND:
        continue
    graph[i].append((i*2,0))

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

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(n,distance,graph)

print(distance[k])