다익스트라 - 4485번: 녹색 옷 입은 애가 젤다지?

우선순위 큐(heap)을 사용하여 다익스트라 구현 -> 낮은 cost의 경로부터 탐색

import heapq

n = int(input())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dijkstra(maps, n):
    dist = [[float('inf')] * n for _ in range(n)] # 모든 거리 무한대로 초기화
    dist[0][0] = maps[0][0]

    heap = []
    heapq.heappush(heap, (maps[0][0], 0, 0))

    while heap:
        cost, x, y = heapq.heappop(heap)

        # 이미 더 짧은 경로로 방문한 경우 패스
        if cost > dist[y][x]:
            continue
        else:
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]

                if 0 <= nx < n and 0 <= ny < n:
                    next_cost = cost + maps[ny][nx]

                    if next_cost < dist[ny][nx]:
                        dist[ny][nx] = next_cost
                        heapq.heappush(heap, (next_cost, nx, ny))

    return dist[n-1][n-1]

pro_num = 1

while True:
    maps = []

    for i in range(n):
        line = list(map(int, input().split()))
        maps.append(line)
    
    res = dijkstra(maps, n)

    print(f'Problem {pro_num}: {res}')

    n = int(input())
    pro_num += 1
    if n == 0:
        break