[백준][Dijkstra/다익스트라] 4885. 녹색 옷 입은 애가 젤다지? (파이썬/Python)

import heapq
import sys

INF =int(1e9)
input = sys.stdin.readline
dx = [0,0,-1,1]
dy = [1,-1,0,0]
tastcase = 1
def dijsktra():
    q = []
    heapq.heappush(q,(graph[0][0],0,0)) #cost, 시작위치 graph[0][0]을 넣어줌
    dist[0][0] = 0 

    while q:
        cost, x,y = heapq.heappop(q)
        if x == n-1 and y == n-1: #도착했다면?
            print(f"Problem {tastcase}: {dist[x][y]}")
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < n:
                newCost = cost + graph[nx][ny]

                #새로운 cost가 현재까지의 cost보다 작다면 그쪽으로 진행한다. 
                if newCost < dist[nx][ny]:
                    dist[nx][ny] = newCost
                    heapq.heappush(q,(newCost,nx,ny))


while True:
    n = int(input())
    if n == 0:
        break
    
    graph = []
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        graph.append(list(map(int,input().split())))
    dijsktra()
    tastcase += 1

# 최소 비용을 구하는 문제인데, 이때 가중치가 존재하기 때문에 BFS로는 구할 수 없다. 

# 각 노드에서 4방향을 다 돌면서 가장 작은 비용으로 이동하는 곳으로 옮겨가며 진행한다. 

# 위의 코드에서 dist --> minCost를 의미한다 ! 

# 또한 다익스트라 알고리즘은 heap을 사용해서 푼다. (BFS는 deque) 

    # heap은 완전 이진 트리의 일종으로 우선 순위 큐를 위해 만들어진 자료구조이다.

    # heap은 최댓값 최솟값을 찾기 위해 만들어졌다.