Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 목적지까지 이동 가능하게 만드는 최소 높이 증가량 찾기

행렬 M이 주어지고, M[r][c]는 해당 셀의 높이를 나타낸다고 가정해 보겠습니다. 우리는 현재 행렬의 왼쪽 위 모서리에 위치해 있으며, 오른쪽 아래 모서리로 이동하고자 합니다. 이때 인접한 셀(위, 아래, 왼쪽, 오른쪽)은 그 셀의 높이가 현재 셀의 높이보다 작거나 같을 경우에만 이동할 수 있습니다.

흥미로운 점은 이동을 시작하기 전에 원하는 만큼 셀의 높이를 올릴 수 있다는 것입니다. 따라서 우리가 구해야 하는 값은, 오른쪽 아래 셀까지 도달할 수 있도록 하기 위해 증가시켜야 하는 높이의 최소 총합입니다.

문제 예시

예를 들어 입력 행렬이 다음과 같다고 해보겠습니다.

245
861

이 경우 정답은 4입니다. 경로 [2, 4, 5, 1]을 선택하고, 일부 셀의 높이를 다음과 같이 조정하면 끝까지 이동할 수 있기 때문입니다.

555
861

풀이 접근 방법

이 문제는 다익스트라(Dijkstra) 알고리즘을 응용하여 해결할 수 있습니다. 상태를 (행, 열, 현재 높이)로 관리하면서, 높이 증가량이 가장 적은 경로부터 탐색해 나가는 방식입니다. 구체적인 단계는 다음과 같습니다.

  • 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에 저장합니다. (d는 누적 증가량, r과 c는 좌표, h는 현재 높이)
    • 만약 dist[r, c, h] < d라면 이미 더 좋은 경로가 발견된 것이므로 다음 반복으로 넘어갑니다.
    • r과 c가 모두 0이라면 출발점에 도달한 것이므로 d를 반환합니다.
    • 인접 좌표 [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]의 각 (nr, nc)에 대해 다음을 수행합니다:
      • 좌표가 행렬 범위 내(0 ≤ nr < R, 0 ≤ nc < C)라면:
      • h2 := max(A[nr][nc], h) — 새로운 셀의 필요 높이를 계산합니다.
      • d2 := d + max(h2 − A[nr][nc], 0) — 해당 셀에서 추가로 올려야 하는 높이를 누적합니다.
      • 만약 d2 < dist[nr, nc, h2]라면:
        • dist[nr, nc, h2] := d2 로 갱신합니다.
        • [d2, nr, nc, h2]를 pq에 삽입합니다.

구현 코드

아래 코드를 통해 더 잘 이해해 보겠습니다.

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]]

출력

4