Pythonで水から最も遠い陸地の距離を求めるプログラムの書き方

0が水、1が陸地を表す2値行列があるとします。ここでの課題は、水からのマンハッタン距離が最も遠い陸地を見つけ、その距離を返すことです。

例として、次のような入力行列を考えてみましょう。

この場合、出力は3となります。左上のセル[0, 0]から最も近い水のセルまでのマンハッタン距離が3であるためです。

解法のアプローチ

この問題は、水のセルを起点とする幅優先探索(BFS)を使うことで効率的に解けます。すべての水セルから同時に探索を広げていくことで、各陸地セルの「最も近い水までの距離」が自然に求まり、その中の最大値が答えになります。手順は以下の通りです。

• 行列Aが空であれば、0を返します。
• Rを行数、Cを列数とします。
• distanceとしてR×Cの行列を作成し、すべて0で初期化します。
• qとして、matrix[r][c]が0(水)であるセルの座標ペア(r, c)をすべて格納した両端キュー(deque)を用意します。
• qのサイズが0(水が存在しない)またはR×C(陸地が存在しない)の場合は、-1を返します。
• qが空になるまで、以下を繰り返します。
  • qの左端から要素(r, c)を取り出します。
  • 隣接セル(r−1, c)、(r+1, c)、(r, c+1)、(r, c−1)のそれぞれについて、(x, y)が行列の範囲内かつA[x][y]が1(未訪問の陸地)であれば、次の処理を行います。
    • A[x][y]を0にして訪問済みにします。
    • distance[x][y]にdistance[r][c] + 1を代入します。
    • (x, y)をqの末尾に追加します。
• 各行の最大値を集めたリストresを作成し、その最大値を返します。

Pythonによる実装例

理解を深めるために、以下の実装を見てみましょう。

from collections import deque

class Solution:
    def solve(self, A):
        # 行列が空の場合は0を返す
        if not A:
            return 0
        R, C = len(A), len(A[0])
        # 距離を記録するR x Cの行列を0で初期化
        distance = [[0] * C for _ in range(R)]
        # 水のセル(値が0)をすべてキューに入れる
        q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c])
        # 水のみ、または陸地のみの場合は-1を返す
        if len(q) in (0, R * C):
            return -1
        # 幅優先探索(BFS)で各陸地セルまでの距離を計算
        while q:
            r, c = q.popleft()
            for x, y in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]:
                if 0 <= x < R and 0 <= y < C and A[x][y]:
                    A[x][y] = 0
                    distance[x][y] = distance[r][c] + 1
                    q.append((x, y))
        # 最大の距離を返す
        return max(max(row) for row in distance)

ob = Solution()
matrix = [
    [1, 1, 1, 1],
    [1, 1, 0, 1],
    [1, 1, 1, 1],
    [0, 0, 1, 1]
]
print(ob.solve(matrix))

入力

[
[1, 1, 1, 1],
[1, 1, 0, 1],
[1, 1, 1, 1],
[0, 0, 1, 1]
]

出力

3

このアルゴリズムの計算量は、セル数をNとするとO(N)であり、各セルを一度だけ訪問するため非常に効率的です。マップ上の地点と最寄りの施設との距離を求めるような実務的な問題にも応用できる手法なので、ぜひ覚えておきましょう。