1. 문제 설명

창영이와 퇴근

2. 문제 분석

다익스트라를 통해 최대 경사의 최솟값을 비용으로 한 최단 거리의 거리 집합을 구한다. 다음 노드로 가는 비용이 현재 비용 또는 경사 중 최댓값임을 주의.

3. 나의 풀이

import sys
import heapq
from collections import deque

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

def Dijkstra():
    distances = [[INF for _ in range(n)] for _ in range(n)]
    distances[0][0] = 0

    pq = []
    heapq.heappush(pq, [0, 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 >= n: continue

            next_cost = max(cur_cost, abs(nodes[cur_row][cur_col]-nodes[next_row][next_col]))
            if distances[next_row][next_col] > next_cost:
                distances[next_row][next_col] = next_cost
                heapq.heappush(pq, [next_cost, next_row, next_col])
    return distances

distances = Dijkstra()
print(distances[n-1][n-1])