Python에서 목적지에 도달하기 위해 증가되어야 하는 최소 높이를 찾는 프로그램

<시간/>

M[r][c]가 해당 셀의 높이를 나타내는 행렬 M이 있다고 가정합니다. 현재 왼쪽 상단 모서리에 있고 오른쪽 하단 모서리로 이동하려는 경우. 인접한 셀의 높이가 현재 셀의 높이보다 작거나 같은 경우에만 인접한 셀(위, 아래, 왼쪽, 오른쪽)로 이동할 수 있습니다. 이동하기 전에 셀의 높이를 얼마든지 늘릴 수 있으므로 오른쪽 아래 셀로 이동할 수 있도록 증가해야 하는 최소 총 높이를 찾아야 합니다.

따라서 입력이 다음과 같으면

2	4	5
8	6	1

다음 경로 [2, 4, 5, 1]를 선택하고 높이를 이 구성으로 변경할 수 있으므로 출력은 4가 됩니다. -

5	5	5
8	6	1

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

INF :=무한대

R, C :=행렬의 행 번호, 행렬의 열 번호
pq :=힙을 사용하여 우선순위 큐를 만들고 [0, R-1, C-1, M[-1, -1]]을 삽입합니다.
dist :=지도
dist[R-1, C-1, A[-1, -1]] :=0
pq가 비어 있지 않은 동안 수행
- pq에서 하나의 요소를 삭제하고 d, r, c, h에 저장
- dist[r, c, h]
  - 다음 반복으로 이동
- r과 c가 모두 0이면
  - 리턴 d
- [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]의 각 쌍(nr, nc)에 대해 수행
  - 0 <=nr
    - d2
      - dist[nr, nc, h2] :=d2
      - pq에 [d2, nr, nc, h2] 삽입

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

import collections
import heapq
class Solution:
   def solve(self, A):
      INF = float('inf')
      R, C = len(A), len(A[0])

      pq = [[0, R-1, C-1, A[-1][-1]]]
      dist = collections.defaultdict(lambda: INF)
      dist[R-1, C-1, A[-1][-1]] = 0
      while pq:
         d, r, c, h = heapq.heappop(pq)
         if dist[r, c, h] < d:
            continue
         if r == c == 0:
            return d
         for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
            if 0 <= nr < R and 0 <= nc < C:
               h2 = max(A[nr][nc], h)
               d2 = d + max(h2 - A[nr][nc], 0)
               if d2 < dist[nr, nc, h2]:
                  dist[nr, nc, h2] = d2
                  heapq.heappush(pq, [d2, nr, nc, h2])
ob = Solution()
matrix = [
[2, 4, 5],
[8, 6, 1]
]
print(ob.solve(matrix))

입력

[[2, 4, 5],[8, 6, 1]]