화성탐사(다익스트라)

우선순위큐를 통해 스타트지점부터 n-1,n-1 지점까지의 최단거리를 확인합니다.최단거리를 기준으로 한 거리를 큐에 계속 삽입시켜 주고 해당 노드들은 distance를 통해 방문했는지 안했는지를 파악하거나 기존 distance보다 현재 노드를 거쳐서 가는 거리가 더 작을 경우 갱신과 동시에 큐에 삽입해줍니다.

 

import heapq

import sys

input = sys.stdin.readline

INF = int(1e9)

 

dx = [-1,1,0,0]

dy = [0,0,1,1]

#

for tc in range(int(input())):

    n = int(input())

    graph = []

    for i in range(n):

        graph.append(list(map(int,input().split())))

 

    distance = [[INF]*n for _ in range(n)]

 

    x, y = 0, 0

    q = [(graph[x][y], x, y)]

    distance[x][y] = graph[x][y]

 

    while q:

        dist, x, y = heapq.heappop(q)

        if distance[x][y] < dist:

            continue

        

        for i in range(4):

            nx= x+dx[i]

            ny= y+dy[i]

            if nx< 0 or nx>=n or ny<0 or ny>=n:

                continue

            cost = dist + graph[nx][ny]

            if cost < distance[nx][ny]:

                distance[nx][ny] = cost

                heapq.heappush(q,(cost,nx,ny))

    

    print(distance[n-1][n-1])