[BOJ 20046, Python 3] Road Reconstruction

https://www.acmicpc.net/problem/20046

20046번: Road Reconstruction

 

 

풀이

일단 BFS를 생각해볼 수 있는데 도로의 비용이 0 또는 1뿐이라면 덱을 활용한 0-1 BFS를 생각해볼 수 있지만, 비용이 0, 1, 2로 총 세가지이기 때문에 BFS로는 풀기 힘들 것 같고, 다익스트라 알고리즘을 사용하면 됩니다.

 

참고로 문제에 (0, 0)의 값이 -1일 수도 있다는 점을 주의해주시면 됩니다.

 

 

코드

from heapq import *
input = __import__('sys').stdin.readline
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
MAX = 987654321
 
m, n = map(int, input().split())
MAP = [[*map(int, input().split())] for _ in range(m)]
S = [[MAX] * n for _ in range(m)]; S[0][0] = MAP[0][0]
q = []; heappush(q, [MAP[0][0], 0, 0]) # 비용, (x, y)
 
if MAP[0][0] == -1:
    print(-1)
    exit()
 
while q:
    t, x, y = heappop(q)
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and MAP[nx][ny] != -1 and S[nx][ny] > t + MAP[nx][ny]:
            S[nx][ny] = t + MAP[nx][ny]
            heappush(q, [S[nx][ny], nx, ny])
print([S[m-1][n-1], -1][S[m-1][n-1] == MAX])