난이도: 2 / 풀이 시간: 40분
당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다.
화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 간인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요.
화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다.
입력 조건
출력 조건
입력 예시
3 3 5 5 4 3 9 1 3 2 7 5 3 7 2 0 1 2 8 0 9 1 1 2 1 8 1 9 8 9 2 0 3 6 5 1 5 7 9 0 5 1 1 5 3 4 1 2 1 6 5 3 0 7 6 1 6 8 5 1 1 7 8 3 2 3 9 4 0 7 6 4 1 5 8 3 2 4 8 3 7 4 8 4 8 3 4
출력 예시
20
19
36
풀이 특징
import sys
import heapq
input = sys.stdin.readline
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
INF = int(1e9)
def dijkstra(graph, n, x, y):
distance = [[INF]*n for _ in range(n)]
distance[x][y] = graph[x][y]
q = []
heapq.heappush(q, (graph[x][y], x, y))
while q:
dist, x, y = heapq.heappop(q)
if distance[x][y] < dist:
continue
for move in moves:
nx = x+move[0]
ny = y+move[1]
if nx < 0 or nx >= n:
continue
if ny < 0 or ny >= n:
continue
cost = graph[nx][ny]
newCost = dist + cost
if newCost < distance[nx][ny]:
distance[nx][ny] = newCost
heapq.heappush(q, (newCost, nx, ny))
return distance
t = int(input())
for _ in range(t):
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
distance = dijkstra(graph, n, 0, 0)
print(distance[n-1][n-1])