[이코테/Python] 화성 탐사 || 최단 경로, 다익스트라

이코테 화성 탐사 파이썬

❍ 문제

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

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

❍ 입력

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

❍ 출력

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

❏ 문제 풀이

(0, 0)에서 (n - 1, n - 1)까지의 최단 경로를 구하는 문제이다.

맵의 각 칸을 노드로 보고, 상하 좌우로 노드가 연결되어있다고 생각하면 된다.

A → B의 비용은 B 위치의 비용, B → A의 비용은 A 위치의 비용이다.

이를 방향 그래프로 표현하면 아래와 같다.

입력 조건의 N의 범위 크기가 125뿐이지만, 2차원이기 때문에, 전체 노드의 개수는 $N^2$이므로 10,000이 넘게 된다. 따라서, 시간 복잡도가 $O(N^3)$인 플로이드 워셜 알고리즘보다 다익스트라 최단 경로 알고리즘을 이용하는 것이 더 효과적이다.

노드의 개수가 V일 때, 시간 복잡도가 $O(V^2)$인 풀이로도 시간 초과 없이 풀이가 될 것 같지만, 우선 순위 큐를 이용하여 좀 더 시간 복잡도가 줄어드는 풀이를 선택하여 풀이하였다.

우선 순위 큐를 이용하면 $O(ElogV)$의 시간복잡도를 가진다.

[Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra

 

 

❍ Code

import sys
import heapq

input = sys.stdin.readline

t = int(input())
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
INF = int(1e9)

for _ in range(t):
    n = int(input())
    graph = [list(map(int, input().split())) for _ in range(n)]

    dp = [[INF] * n for _ in range(n)]
    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))
    dp[0][0] = graph[0][0]

    while q:
        dist, x, y = heapq.heappop(q)

        if dp[x][y] < dist:
            continue

        for dx, dy in direction:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            cost = dist + graph[nx][ny]
            if cost < dp[nx][ny]:
                dp[nx][ny] = cost
                heapq.heappush(q, (cost, nx, ny)) 

    print(dp[-1][-1])