[이것이 코딩테스트다] 화성 탐사

🗃️문제 설명

당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다. 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다.

첫째 줄에 테스트 케이스의 수(1 ≤ T ≤ 10)가 주어집니다.
매 테스트 케이스의 첫째 줄에는 탐사 공간의 크기를 의미하는 정수 N이 주어집니다. (2 ≤ N ≤ 125)
이어서 N개의 줄에 걸쳐 각 칸의 비용이 주어지며 공백으로 구분합니다. (0 ≤ 각 칸의 비용 ≤ 9)

각 테스트 케이스마다 [0][0]의 위치에서 [N-1][N-1]의 위치로 이동하는 최소 비용을 한 줄에 하나씩 출력합니다.

🖥️코드

import sys, heapq
input = sys.stdin.readline

def dijkstra(a, b):
    global distance
    q = []
    heapq.heappush(q, (maps[a][b], a, b))
    distance[a][b] = 0  # 자기 자신으로 가는 경로 0
    dy = [-1, 0 ,1, 0]
    dx = [0, -1, 0, 1]
    while q:
        dist, y, x = heapq.heappop(q)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or ny >= N or nx < 0 or nx >= N:
                continue
            if 0 <= ny < N and 0 <= nx < N:
                cost = dist + maps[ny][nx]
                if distance[ny][nx] < cost:
                    continue
                distance[ny][nx] = min(distance[ny][nx], cost)
                heapq.heappush(q, (cost, ny, nx))

T = int(input())
for _ in range(T):
    inf = float('inf')
    N = int(input())
    distance = [[inf] * (N+1) for _ in range(N+1)]                      # 최단 경로 테이블 
    maps = [list(map(int, input().split())) for _ in range(N)]
    dijkstra(0, 0)
    print(distance[N-1][N-1])

🧠아이디어

알고리즘 유형 : 최단 경로 알고리즘(다익스트라)

개선된 다익스트라 알고리즘(힙을 사용)을 사용하여 작성, 최단 경로 테이블은 각 좌표에 도달할 때 소모하는 최소 에너지 소모량이므로 2차원 테이블로 작성

🔒문제 출처 및 참고 코드

이것이 코딩테스트다 with 파이썬 - 화성 탐사
모범 답안 - 화성 탐사