[이코테] 최단 경로 - 화성 탐사

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

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

입력조건

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

출력조건

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

사고과정

• '에너지를 효율적으로 사용 ~ 출발 지점에서 목표 지점까지 이동' 키워드를 보고 특정 노드에서 다른 노드까지 도달하는 최단 경로를 구해야 한다라는 것을 캐치했고 바로 다익스트라 알고리즘을 떠올렸다. 시간 내에는 풀지 못했지만 끝까지 매달려서 풀었다!
• 2차원 리스트로 들어오는 것을 인접 리스트? 인접 행렬 형태로 어떻게 표현해야 할지.. 거리 테이블을 2차원으로 해야할지..에 대해 고민하는 시간을 좀 많이 썼다. 결론은 인접 행렬 형태로 표현하면 되게 된다! 단, (x, y) 좌표 값 하나를 노드로 보는데, (x, y) 에서 또 다른 (x, y)로 가는 비용은 도착하는 (x, y)좌표의 값으로 한다. 예를 들어, (1, 1) -> (1, 2) 로 가는 비용은 (1, 2) 좌표에 있는 값으로 한다! 거리 테이블도 2차원으로 하는게 맞았다. 그래서 인접 행렬, 거리 테이블 2개로 2차원 리스트를 운용하면서 거리 테이블에는 시작 점으로부터 최단 거리를 갱신하고 인접 행렬에서는 해당 좌표로 갈 때마다 드는 비용을 참조하기 위해 사용하면 된다.
• 시간 복잡도를 고려하여 우선순위 큐(heapq)를 활용
• 간만에 혼자 풀 수 있는 문제였다...🥲

풀이

 1. 책 속의 풀이와 동일했다.

import heapq

for _ in range(int(input())):
    n = int(input())
    INF = int(1e9)
    graph = []
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    distance = [[INF] * n for _ in range(n)]

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))  # cost, x, y
    distance[0][0] = graph[0][0]
    while q:
        dist, x, y = heapq.heappop(q)
        if dist > distance[x][y]:
            continue
        for i in range(4):
            nx, ny = x + dx[i], 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])