- 칸에 도착할 경우에도 에너지가 소모되므로, 이 경우 최단 거리 return 시 마지막 칸의 값을 별도로 더해주어야한다.
풀이 : 우선순위 큐
import sys
from heapq import heappop, heappush
INF = float('inf')
def solution(n, mars):
# 다익스트라 -> 하나의 점에서 다른 점까지의 최소 가리
# 상하좌우로만 간선이 그어진 그래프
# 칸에서 나가는 간선은 칸을 지나가기 위한 비용
# return 시 마지막 칸에 도달 시 칸 비용 + 해줘야함.
# 노드의 개수
NC = n ** 2
# 가중치 그래프
matrix = [[INF if i != j else 0 for j in range(NC)] for i in range(NC)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 그래프 초기화
for r in range(n):
for c in range(n):
cur_idx = r * n + c
for dr, dc in direction:
nr, nc = r + dr, c + dc
if not 0 <= nr < n or not 0 <= nc < n:
continue
target_idx = nr * n + nc
# current_node -> target_node : mars[r][c]
matrix[cur_idx][target_idx] = mars[r][c]
# 다익스트라
min_distance = [INF for _ in range(NC)]
min_distance[0] = 0
heap = []
heappush(heap, (0, 0))
visited_node = set()
while len(heap) > 0:
# 가장 짧은 거리인 노드를 뺸다.
dis_until_current_node, node_idx = heappop(heap)
# 방문하지 않았다면, 방문 체크
if node_idx in visited_node:
continue
visited_node.add(node_idx)
# 현재 노드의 거리 값 + 인접한 노드의 거리 값을 인접 노드까지 최소 거리로 업데이트
# 인접 노드를 거리값을 우선 순위로 heap에 넣음
current_node_dis = min_distance[node_idx]
for near_node_idx in range(NC):
near_node_dis = matrix[node_idx][near_node_idx]
# 인접하지 않다면 패스
if near_node_dis == INF:
continue
# 인접한 노드에 한해 최소 거리 갱신
min_distance[near_node_idx] = min(min_distance[near_node_idx], current_node_dis + near_node_dis)
# 갱신된 최소 거리를 우선순위로 인접한 노드를 우선순위 큐에 넣음
heappush(heap, (min_distance[near_node_idx], near_node_idx))
return min_distance[NC - 1] + mars[n-1][n-1]
n = int(input())
mars = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
print(solution(n, mars))
