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

파이썬(Python)으로 최대 최소 경로 찾기: 힙 기반 그리디 알고리즘

문제 정의

R개의 행과 C개의 열로 구성된 정수 행렬 A가 주어졌을 때, [0, 0]에서 시작하여 [R-1, C-1]에서 끝나는 경로 중 최대 점수를 얻는 경로를 찾아야 합니다. 이때 경로의 점수는 해당 경로에 포함된 값들 중 최솟값으로 정의됩니다. 예를 들어, 경로 8 → 4 → 5 → 9의 점수는 4입니다.

경로는 이미 방문한 칸에서 북, 동, 서, 남 네 방향 중 하나로 인접한 아직 방문하지 않은 칸으로 여러 번 이동하는 방식으로 확장됩니다.

예시

다음과 같은 격자가 있다고 가정해 보겠습니다 −

545
126
746

주황색으로 표시된 칸이 선택한 경로이며, 경로 5 → 4 → 5 → 6 → 6 중 최솟값은 4이므로 결과는 4가 됩니다.

접근 방법

이 문제는 그리디(Greedy) 기법과 최대 힙(Max Heap)을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 매 단계마다 현재 도달 가능한 칸 중 값이 가장 큰 칸부터 우선적으로 방문하는 것입니다. 이렇게 하면 목적지에 도달하는 시점의 최솟값이 자연스럽게 최대화됩니다.

파이썬의 heapq 모듈은 최소 힙만 지원하므로, 행렬 값을 음수로 변환해 저장하면 최대 힙처럼 동작하게 만들 수 있습니다.

알고리즘 단계

  • r := 행의 개수, c := 열의 개수
  • ans := min(A[0, 0], A[r-1, c-1])
  • A와 같은 크기의 visited 행렬을 만들고 False로 초기화
  • h := (-A[0, 0], 0, 0) 튜플을 담은 리스트
  • h를 힙으로 변환(heapify)
  • h가 비어 있지 않은 동안 반복:
    • v, x, y := 힙에서 원소를 꺼내 세 값 저장
    • x == r-1이고 y == c-1이면 루프 탈출
    • ans := min(ans, A[x, y])
    • visited[x, y] := True
    • [(-1, 0), (1, 0), (0, 1), (0, -1)]의 각 방향 (dx, dy)에 대해:
      • a := x + dx, b := y + dy
      • (a, b)가 행렬 범위 안에 있고 아직 방문하지 않았다면 (-A[a][b], a, b)를 힙에 삽입
  • ans 반환

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다 −

구현 예제

import heapq
class Solution(object):
    def maximumMinimumPath(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        r,c = len(A),len(A[0])
        ans = min(A[0][0],A[-1][-1])
        visited = [[False for i in range(c)] for j in range(r)]
        h = [(-A[0][0],0,0)]
        heapq.heapify(h)
        while h:
            v,x,y = heapq.heappop(h)
            if x== r-1 and y == c-1:
                break
            ans = min(ans,A[x][y])
            visited[x][y]= True
            for dx,dy in {(-1,0),(1,0),(0,1),(0,-1)}:
                a,b = x+dx,y+dy
                if a>=0 and a<r and b>=0 and b<c and not visited[a][b]:
                    heapq.heappush(h,(-A[a][b],a,b))
        return ans

입력

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

출력

4