[백준] 22116번 - 창영이와 퇴근 (파이썬)

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

 

# 창영이와 퇴근
import sys
import heapq
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
visited = [[sys.maxsize for _ in range(N)]for _ in range(N)]


def dijkstra(a, b):
    q = []
    heapq.heappush(q, (0, a, b))
    visited[a][b] = 0
    while q:
        height, x, y = heapq.heappop(q)
        if visited[x][y] < height:
            continue
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < N:
                nheight = max(height, abs(arr[nx][ny]-arr[x][y]))
                if visited[nx][ny] > nheight:
                    visited[nx][ny] = nheight
                    heapq.heappush(q, (nheight, nx, ny))


dijkstra(0, 0)
print(visited[N-1][N-1])

 

최단거리, 다익스트라
1. 입력을 받는다.
2. 다익스트라
    - 연결된 노드 탐색 (리스트 범위 내의 상하좌우 탐색)
    - 해당 기울기가 기존 경사보다 작다면 q에 append, visited에 기록
3. 목적지의 최종 경사 출력

 

(1, 1)에서 시작해서 (N, N)까지 연결된 모든 노드를 탐색하면서 가장 높은 경사를 기록해준다.

리스트 구조상 각 연결된 노드가 붙어있으므로 MST로 봐도 무방한 것 같다.