이번 문제는 다익스트라 알고리즘을 활용하여 해결하였다. 다익스트라에 사용되는 가중치 리스트를 거리에 대한 가중치가 아닌, 경사에 대한 가중치로 설정하였고, 다음 가중치를 결정할 때에는 현재 경사와 다음 칸과 현재 칸 간의 차이 중 더 큰 값으로 결정하였고, 이 가중치보다 다음 칸의 가중치가 더 클 경우에만 최소힙에 넣어 탐색을 진행하였다.

Code

import heapq
n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
sy, sx = 0, 0
def find_way():
    q = []
    heapq.heappush(q, (0, sy, sx))
    costs = [[1e9 for _ in range(n)] for _ in range(n)]
    costs[sy][sx] = 0
    while q:
        cost, y, x = heapq.heappop(q)
        if cost > costs[y][x]:
            continue
        if (y, x) == (n-1, n-1):
            return cost
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                nxt_cost = max(abs(grid[ny][nx] - grid[y][x]), cost)
                if costs[ny][nx] > nxt_cost:
                    costs[ny][nx] = nxt_cost
                    heapq.heappush(q, (nxt_cost, ny, nx))
    return -1
print(find_way())