백준 22116 : 창영이와 퇴근 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline
INF=int(1e9)
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def Dijkstra():

    dp=[ [INF]*(N+1) for _ in range(N+1) ]

    heap=[] ; heapq.heappush(heap,(0 , 0 , 0 , 0))

    while heap:

        value,x,y,total=heapq.heappop(heap)

        if x==N-1 and y==N-1:
            return total
        if dp[x][y]<value:
            continue
        for i in range(4):
            nx=x+dx[i] ; ny=y+dy[i]

            if 0<=nx<N and 0<=ny<N:

                if abs(graph[x][y]-graph[nx][ny])<dp[nx][ny]: #다음으로 이동할 거리가 현재까지 이동한 거리보다 작다면.
                    dp[nx][ny]=abs(graph[x][y]-graph[nx][ny])
                    heapq.heappush(heap,(abs(graph[x][y]-graph[nx][ny]) , nx , ny , max(total ,dp[nx][ny])))


N=int(input())
graph=[ list(map(int,input().split())) for _ in range(N) ]

print( Dijkstra() )

📌 어떻게 접근할 것인가?

처음에는 $MST$ 로 풀었습니다. 크루스칼 알고리즘을 사용하니 이동가능한 간선의 개수가 대부분의 노드마다 상하좌우로 이동가능하다보니 시간초과가 났습니다.

그래서 프림알고리즘으로 해봤는데 잘 안풀려서 다익스트라 알고리즘을 사용했습니다.

이동가능한 정점에 대해서 절대값을 구한뒤에 최단경로로 이동했습니다.

하지만 문제에서 원하는 것은 최단경로로 이동한 값중 최대값을 구해야 하므로
heap 배열에 최단경로의 값과 , 좌표값 그리고 마지막에 최대경사를 매번 저장했습니다.

이후 좌표의 끝에 도착하면 저장해놨던 최대경사를 return 하였습니다.