문제
화성 탐사 기계가 출발 지점에서 목표 지점까지 이동 할 떄 최적의 경로를 찾도록 개발해야 함
화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재한다.
가장 왼쪽 위 칸인 [0][0]에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하시오.
화성 탐사 기계는 특정한 위치에서 상하 좌우 인접한 곳으로 1칸씩 이동할 수 있다.
입력
첫째 줄에 테스트 케이스의 수 T가 주어짐, 매 테스트 케이스의 첫째 줄에는 N이 주어짐,
이어서 N개의 줄에 걸쳐 각 칸의 비용이 주어지며 공백으로 구분됨
출력
각 테스트 케이스마다 [0][0] 에서 [N-1][N-1]까지 이동하는 최소 비용을 한 줄에 하나씩 출력
풀이
# 17-39) 화성 탐사
def renew_distance(x, y, dist):
if x < 0 or x > n-1 or y < 0 or y > n-1: return
if visited[x][y]: return
if dist + cost[x][y] < distance[x][y]:
distance[x][y] = dist + cost[x][y]
heapq.heappush(hp, (distance[x][y], x, y))
import sys, heapq
result = []
INF = int(1e9)
t = int(input())
for _ in range(t):
n = int(input())
cost = []
for _ in range(n):
cost.append(list(map(int, sys.stdin.readline().split())))
distance = [[INF for _ in range(n)] for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]
distance[0][0] = cost[0][0]; visited[0][0] = True
hp = []
heapq.heappush(hp, (distance[0][0], 0, 0))
while hp:
dist, x, y = heapq.heappop(hp)
if dist > distance[x][y]: continue
visited[x][y] = True
renew_distance(x-1, y, dist)
renew_distance(x, y-1, dist)
renew_distance(x+1, y, dist)
renew_distance(x, y+1, dist)
result.append(distance[n-1][n-1])
for x in result: print(x)