[백준 알고리즘] 22116번: 창영이와 퇴근 (Python)

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

22116번: 창영이와 퇴근

 

소스코드

import sys
import heapq as hq
input = sys.stdin.readline

nx = [-1,0,1,0]
ny = [0,1,0,-1]
def dijkstra():
  q = []
  hq.heappush(q,[0,0,0])
  min_dis[0][0] = 0

  while q:
    h,x,y = hq.heappop(q)

    
    if min_dis[x][y] < h:
      continue

    for i in range(4):
      xx = x + nx[i]
      yy = y + ny[i]

      if (0 <= xx < n) and (0 <= yy < n):
        height = max(h,abs(graph[x][y] - graph[xx][yy]))
        if min_dis[xx][yy] > height:
          min_dis[xx][yy] = height
          hq.heappush(q,[height,xx,yy])

  return min_dis

n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
min_dis = [[float('inf') for _ in range(n)] for _ in range(n)]
dijkstra()
print(min_dis[n-1][n-1])

 

풀이

★ 각각의 위치의 경사를 저장하는 min_dis 배열을 2차원 배열로 설정한 뒤 기록해줍니다 ! 이 때 최대 경사의 최솟값을 구해야 하기 때문에, max()함수를 사용하여, 현재 경사와 다음 경사의 최댓값을 찾아서 그 값으로 min_dis를 갱신시켜 나가야 합니다 !!