백준 13549. 숨바꼭질 3 메모리 최적화를 향하여 - 데이크스트라 알고리즘을 사용한 풀이

from heapq import *


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

if start >= end:
    print(start-end)
    exit()
    
if end == 1:
    print(1)
    exit()

graph = {start: [(start+i, j) for (i, j) in [(-1, 1), (1, 1), (start, 0)] if 0 <= start+i < 100_001]}

# 데이크스트라
def d(start: int, end: int):
    heap = [(0, start)]
    while heap:
        cost_from_start, current_node = heappop(heap)
        if current_node == end:
            print(cost_from_start)
            return 
        while graph[current_node]:
            next_node, cost = graph[current_node].pop()
            if next_node in graph:   # if next_node is already visited
                continue
            c = cost_from_start + cost
            
            # 그래프 그리기
            graph[next_node] = []
            for i, j in [(-1, 1), (1, 1), (next_node, 0)]:
                if 0 <= next_node+i < 100_001:
                    graph[next_node].append((next_node+i, j))
            
            heappush(heap, (c, next_node))

d(start, end)

1. visited 세트를 따로 만들지 않았다. 대신 딕셔너리 graph를 활용했다.
2. 그래프 키는 리스트로 만들었다. pop하면서 리스트의 크기를 줄여나가 메모리를 최적화했다.
3. 시작점으로부터 모든 노드까지 일일이 거리를 다 기록하지 않도록 작성했다.

데이크스트라 알고리즘을 연습하고 있었기 때문에 BFS나 동적 계획법으로 풀지 않았다. 이 코드보다 성능이 좋았던 코드 대부분은 다이나믹 프로그래밍이나 너비우선탐색을 사용한 코드였다. 위 코드는 시간 164ms를 기록한 코드 중에서 가장 많은 메모리(약 48MB)를 사용하지만, 어떤 bfs보다는 빨랐다. 요즘 백준 시간 측정을 어디까지 믿어야 하나 하는 생각이 들고 있지만 일단 기록해둔다.