문제설명

화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다.

• 입력
  • 첫째 줄에 테스트 케이스의 수 T(1 <= T <= 10)가 주어집니다.
  • 매 테스트 케이스의 첫째 줄에는 탐사 공간의 크기를 의미하는 정수 N이 주어집니다. 이어서 N개의 줄에 걸쳐 각 칸의 비용이 주어지며 공백으로 구분합니다.
• 출력
  각 테스트 케이스마다 [0][0] 위치에서 [N-1][N-1]의 위치로 이동하는 최소 비용을 한 줄에 하나씩 출력합니다.

접근

각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재
최소 비용을 출력
최소비용을 구하는 문제로 다익스트라 알고리즘을 사용하여 풀이가능
특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동
좌표를 설정하여 특정 위치에서의 좌표값을 나타낼 수 있음

풀이

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

# 좌표 설정
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 입력값 받기
test_case = int(input())
for _ in range(test_case):
  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])


                                

배운점

• dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1] for i in range(4): nx = x + dx[i], ny = y + dy[i]와 같이 x, y 각각의 좌표쌍에 대하여 배열로 표현이 가능함
• 우선순위큐를 최소힙으로 구현한 후 다익스트라 알고리즘에서 최단경로지점 갱신에 사용할 수 있음