Pythonで解く「最小値が最大となる経路」問題 ― ヒープを使った貪欲法アルゴリズム

R行C列の整数で構成される行列Aが与えられます。このとき、左上のセル [0, 0] を出発点とし、右下のセル [R-1, C-1] を終点とする経路の中から、「経路上のセルのうち最小の値」をスコアとしたとき、そのスコアが最大になる経路を見つけます。

例えば、ある経路が 8 → 4 → 5 → 9 と辿るとき、経路上の最小値は 4 なので、この経路のスコアは 4 となります。経路は、現在いるセルから上下左右の4方向（北・東・南・西）にある未訪問セルへ移動することで伸ばしていきます。

具体例

次のようなグリッドを考えてみましょう。

オレンジ色で示されたセルが最適な経路です。この経路上の最小値は 4 であるため、出力は 4 となります。

解法のアプローチ

この問題は、優先度付きキュー（ヒープ）を活用した貪欲法で効率的に解けます。ポイントは、常に「値が大きなセルから優先的に探索を進める」ことです。そうすることで、ゴールに到達した時点で得られる答えが最適解であることが保証されます。

具体的な手順は以下の通りです。

• r := 行数、c := 列数 とします
• ans := A[0, 0] と A[r-1, c-1] の最小値で初期化します
• A と同じサイズの訪問管理用行列 visited を作成し、すべて FALSE で埋めます
• h := (-A[0, 0], 0, 0) を格納するリストを作成します
• h をヒープ化します（Python の heapq は最小ヒープのため、値を負にすることで「値が大きいセルほど先に取り出される」最大ヒープとして動作させます）
• h が空でない間、以下を繰り返します
  • v, x, y := ヒープから先頭の要素を取り出し、3つの値として受け取ります
  • x = r-1 かつ y = c-1 であれば、ゴールに到達したためループを抜けます
  • ans := ans と A[x, y] の小さい方に更新します
  • visited[x, y] := True として訪問済みにします
  • 移動方向のリスト [(-1, 0), (1, 0), (0, 1), (0, -1)] の各要素 dy, dx について
    • a := x + dx、b := y + dy とします
    • a が 0 ～ r-1、b が 0 ～ c-1 の範囲内にあり、かつ visited[a, b] が False の場合は、(-A[a, b], a, b) をヒープ h に挿入します
• ans を返します

Pythonによる実装例

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

計算量の目安

時間計算量: O(R × C × log(R × C)) — 各セルは高々一度ずつヒープへの挿入・削除が行われるためです。
空間計算量: O(R × C) — 訪問管理配列とヒープの保存に必要なメモリ量です。

同様の問題は二分探索＋DFS/BFSやUnion-Findでも解けますが、ヒープを使った貪欲法は実装がシンプルで直感的なため、面接などでもよく採用されるアプローチです。