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

문제

 

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

---

Algorithm

다익스트라 탐색

X - 1 칸, X + 1 칸, 2 * X 칸 이동을 각 각 하나의 간선으로 생각하여 구현하면 되는 문제이다. 다만 조건에 유의해야 할 필요가 있다. N과 K의 관계를 유의하자.

 

---

 

 

Code

import heapq
input = __import__('sys').stdin.readline

def dijkstrat(start) :
    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] :
            if i[0] < 0 or i[0] >= sizeG * 2  + 1:
                continue
            cost = dist + i[1]
            
            if cost < distance[i[0]] :
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

N, K = map(int, input().rstrip().split())
sizeG = max(N, K)

graph = [[] for i in range(sizeG * 2 + 1)]
distance = [1e9] * (sizeG * 2 + 1)

for i in range(sizeG * 2 + 1) :
    graph[i].append((i - 1, 1))
    graph[i].append((i + 1, 1))
    graph[i].append((i * 2, 0))

dijkstrat(N)

print(distance[K])

 

느낀 점

처음 풀 때 가장 오래 생각했던 것은 2 * X 칸 이동이 있기 때문에 만약 그래프를 구현한다면 최대 2 * K 칸의 위치도 생각해서 구현해야 하므로 메모리에 관한 걱정이 있었다. 다만 실제 해본 결과, 계산해본 결과 메모리 제한에는 걸리지 않았다. 더 효율적으로 메모리를 사용하는 방안은 무엇이 있을지 고민해보게 되었다. 또한 N < K 라는 규칙은 없어서 처음에 조금 애를 먹었다.