[BOJ] 20046 - Road Reconstruction (Python)

 

 

아이디어

 

다익스트라로 최소 도로 건설 비용을 구해 나간다.

 

 

풀이

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

INF = int(1e7)

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    m, n = map(int, input().split())
    board = [tuple(map(int, input().split())) for _ in range(m)]
    D = [[INF]*n for _ in range(m)]
    heap = []
    if board[0][0] != -1 and board[-1][-1] != -1:
        heap = [(board[0][0], 0, 0)]
    while heap:
        cost, r, c = heappop(heap)
        if D[r][c] < cost:
            continue
        for dr, dc in delta:
            nr, nc = r+dr, c+dc
            if m > nr >= 0 and n > nc >= 0:
                if board[nr][nc] != -1 and D[nr][nc] > cost+board[nr][nc]:
                    D[nr][nc] = cost+board[nr][nc]
                    heappush(heap, (cost+board[nr][nc], nr, nc))
    if D[-1][-1] < INF:
        print(D[-1][-1])
    else:
        print(-1)

solution()