Q39. 화성 탐사

[ACM-ICPC] 화성탐사 — 열정은 차갑고 잔잔하게 (tistory.com)ㅁ

[ACM-ICPC] 화성탐사

 

N * N grid를 그래프 삼아 다익스트라를 수행하면 된다. 2차원리스트이기 때문에 최단경로 저장 리스트 역시 2차원. 2차원 버전의 다익스트라라고 보면 될거같다.

 

import heapq

N = int(input())
INF = 1e10

grid = []
for _ in range(N):
    grid.append(list(map(int,input().split())))

#padding
grid = list(map(lambda x: [-INF] + x + [-INF],  grid))
grid.insert(0, [-INF] * (N + 2))
grid.append([-INF] * (N + 2))

cost = [[INF] * (N + 2) for _ in range(N + 2)]

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

q = []

cost[1][1] = grid[1][1]
heapq.heappush(q, (cost[1][1],1,1) )

while q:
    cur_cost, row, col = heapq.heappop(q)

    if row == 0 or col == 0 or row == N + 1 or col == N + 1:
        continue

    if cost[row][col] < cur_cost:
        continue

    for i in range(4):
        nxt_row = row + dx[i]
        nxt_col = col + dy[i]
        nxt_cost = grid[nxt_row][nxt_col] + cur_cost

        if cost[nxt_row][nxt_col] > nxt_cost:
            cost[nxt_row][nxt_col] = nxt_cost
            heapq.heappush(q,(nxt_cost, nxt_row, nxt_col))

print(cost[N][N])