BOJ 20046번: Road Reconstruction

호프 2021. 2. 13. 03:04

www.acmicpc.net/problem/20046

20046번: Road Reconstruction

입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각

www.acmicpc.net

아이디어:

차량은 가로나 세로방향으로만 움직이므로 현재 위치에 인접한 정점은 상하좌우 좌표라고 할 수 있다.

그럼 인접한 정점을 이동하면서 최소 비용을 업데이트하면 되지 않을까? 했는데 해결됐다!ㅎㅎ

그냥 다익스트라 알고리즘과 똑같이 구현하면 된다.

import sys, heapq

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

xx = [1,-1,0,0]
yy = [0,0,1,-1]
INF = 9999999
ans = [[INF]*n for _ in range(m)]

def solve(X, Y):
    if (graph[Y][X]==-1):
        print(-1)
        sys.exit(0)
    h = []
    ans[Y][X] = graph[Y][X]
    heapq.heappush(h, [ans[Y][X],X,Y])

    while(h):
        now_cost, now_x, now_y = heapq.heappop(h)

        if (now_cost>ans[now_y][now_x]): continue

        for i in range(4):
            x = now_x + xx[i]
            y = now_y + yy[i]
            
            if (x>=0 and x<n and y>=0 and y<m):
                if(graph[y][x]==-1): continue
                cost = now_cost + graph[y][x]
                if (cost<ans[y][x]):
                    ans[y][x] = cost
                    heapq.heappush(h, [ans[y][x], x, y])
    if (ans[m-1][n-1]==INF): print(-1)
    else: print(ans[m-1][n-1])

solve(0,0)