1. 문제 설명

Road Reconsturction

2. 문제 분석

2차원 배열로 그래프를 입력받고, 상하좌우 연결된 간선이라 생각하자. 다익스트라 알고리즘을 통해 입력된 값이 최소가 되는 루트를 찾을 수 있다. 도착지에 도착 가능할 때 그 최소 거리를 출력한다. 이때 시작점

3. 나의 풀이

import sys
import heapq

INF = sys.maxsize
n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = []
for _ in range(n): nodes.append(list(map(int, sys.stdin.readline().rstrip().split())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def Dijkstra():
    distances = [[INF for _ in range(m)] for _ in range(n)]
    distances[0][0] = nodes[0][0]
    pq = []
    if distances[0][0] == -1: return INF
    else: heapq.heappush(pq, [distances[0][0], 0, 0])
    # 시작지가 -1이면 이동 자체가 불가능
    # 시작할 때 사용하는 비용은 0 이나리 nodes[0][0]임을 주의

    while pq:
        cur_cost, cur_row, cur_col = heapq.heappop(pq)

        if distances[cur_row][cur_col] < cur_cost: continue

        for x, y in zip(dx, dy):
            next_row, next_col = cur_row + y, cur_col + x
            if next_row < 0 or next_col < 0 or next_row >= n or next_col >= m: continue
            next_cost = nodes[next_row][next_col]
            if distances[next_row][next_col] > cur_cost + next_cost and next_cost != -1:
                distances[next_row][next_col] = cur_cost + next_cost
                heapq.heappush(pq, [cur_cost + next_cost, next_row, next_col])

    return distances[n-1][m-1]

answer = Dijkstra()
if answer == INF: print(-1)
else: print(answer)