Pythonで行列の外へ出られない陸地セル(島)の数を求めるプログラム

問題概要

0と1だけで構成された2次元のバイナリ行列を考えます。1は陸地、0は水を表します。任意の陸地セルからは、上下左右の4方向にのみ移動が可能で、斜め方向への移動や行列の外へ出ることはできません。このとき、「行列の外へ歩いて出られない陸地セル」の数を求めるのが本記事のテーマです。

たとえば、次のような入力が与えられたとします。

この場合の出力は4となります。中央に位置する4つの陸地セルは、どの方向に進んでも行列の外へ出ることができないためです。

解決のためのアプローチ

この問題は「境界(端)に接する陸地からスタートして、到達できる陸地をすべて除外し、残った陸地の数を数える」という発想で解けます。具体的には幅優先探索(BFS)を利用します。手順は以下の通りです。

1. 境界セルの収集: 行列の最上行・最下行・最左列・最右列にあり、かつ値が1(陸地)であるセルの座標 (i, j) をすべてキュー q に追加します。
2. 初期化: インデックス idx を 0 に設定します。
3. 境界セルの除去: キューに入っている各セル (x, y) に対して、matrix[x][y] を 0 に書き換えます(海に沈めた状態にします)。
4. BFSによる探索: idx がキューのサイズ未満である間、次を繰り返します。
   • キューから (x, y) を取り出します。
   • 4方向 (-1, 0)、(0, -1)、(0, 1)、(1, 0) それぞれについて、隣接セル (nx, ny) を確認します。
   • nx・ny が行列の範囲内で、かつ matrix[nx][ny] が 1 ならば、そのセルを 0 にしてキューの末尾に追加します。
5. 結果の取得: 最後に行列全体の要素の合計値を返します。これが「外に出られない陸地セル」の数になります。

なぜこの方法でうまくいくのか?

行列の外に出られる陸地セルは、必ずどこかの境界セルとつながっています。逆に言えば、境界から到達できない陸地こそが「孤立した島」です。BFSによって境界から到達可能な陸地をすべて0(水)に変換すれば、行列に残った1の個数がそのまま答えになります。

Pythonでの実装例

理解を深めるために、実際のコードを見てみましょう。

def solve(matrix):
    # 境界にある陸地セルをすべて収集
    q = [(i, j) for i in range(len(matrix))
         for j in range(len(matrix[i]))
         if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
    idx = 0
    # 境界の陸地を0に置き換え
    for x, y in q:
        matrix[x][y] = 0
    # BFSで境界から到達できる陸地をすべて除去
    while idx < len(q):
        x, y = q[idx]
        for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
                matrix[nx][ny] = 0
                q.append((nx, ny))
        idx += 1
    # 残った陸地セルの合計が答え
    return sum(sum(row) for row in matrix)

matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))

入力

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

出力

4

計算量

このアルゴリズムでは、各セルは高々1回ずつキューに追加され、各セルにつき4方向をチェックするだけなので、時間計算量は O(行数 × 列数)、空間計算量も同様に O(行数 × 列数) です。行列サイズが大きくなっても効率的に動作します。