[최단경로] 화성탐사

[ericagong]

⭐ 성찰

1. 3차원 리스트 그래프 초기화하는 코드 작성하는 법 기억해두기
2. 다익스트라 알고리즘을 위해 사용하는 heapq에 원하는 형태로 원소 집어넣되, 항상 비용이 앞에 와야함.
3. 상하좌우 이동시 dx, dy, cx, cy, nx, ny 사용하고, 접근 불가 구역에 대한 방어코드 필수임.

❓ 문제 상황

[화성탐사](이코테 p.388)

👨‍💻 문제 해결: 다익스트라 알고리즘

✅ 1차 풀이: 키워드

1. Input 받아 상,하,좌,우가 연결된 그래프 생성하기
2. 생성한 그래프 기반으로 다익스트라 진행(시작점 0,0)
3. d[n-1][n-1] 출력

# 화성탐사 (이코테 p.388)

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
INF = int(2e9)
t = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def solution():
    n = int(input())
    g = [[list() for _ in range(n)] for _ in range(n)]
    d = [[INF] * n for _ in range(n)]
    c = [list(map(int, input().split())) for _ in range(n)]

    for x in range(n):
        for y in range(n):
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    g[x][y].append(((nx, ny), c[nx][ny]))

    dijkstra(0, 0, d, c, g)

    print(d[n - 1][n - 1])

def dijkstra(sx, sy, d, c, g):
    hq = []
    d[sx][sy] = c[sx][sy]
    heappush(hq, (d[sx][sy], (sx, sy)))
    while hq:
        cd, cn = heappop(hq)
        cx, cy = cn
        if d[cx][cy] < cd:
            continue
        for item in g[cx][cy]:
            adjn, edge = item
            adjx, adjy = adjn
            new_cost = cd + edge
            if new_cost < d[adjx][adjy]:
                d[adjx][adjy] = new_cost
                heappush(hq, (d[adjx][adjy], (adjx, adjy)))

for _ in range(t):
    solution()