Pythonで行列内の「完全に囲まれた島」の数を数える方法を解説

問題の概要

0と1のみで構成された2次元のバイナリ行列を考えます。ここで「1」は陸地、「0」は水を表します。島とは、隣り合った1の集まりであり、その周囲がすべて水で囲まれている領域のことです。本記事では、行列の中から端(境界)に一切接しておらず、完全に水で囲まれた島の数を数えるプログラムをPythonで実装する方法を解説します。

例として、次のような入力が与えられた場合を考えてみましょう。

この場合の出力は 2 となります。島は全部で3つ存在しますが、そのうち2つだけが完全に水で囲まれているためです。

解法のアプローチ:DFS(深さ優先探索)

この問題は、DFS(深さ優先探索)を用いることで効率的に解くことができます。ポイントは、島を探索する過程で「行列の端に到達したかどうか」を判定することです。端に到達した島は「完全に囲まれていない」とみなします。

dfs() 関数の定義

• 引数として座標 i, j を受け取ります。
• i または j が行列の範囲外の場合 → False を返す(島が端に達していることを意味する)
• matrix[i][j] が 0(水)の場合 → True を返す
• matrix[i][j] を 0 に更新し、訪問済みとしてマークする
• 上下左右の4方向に対して再帰的に dfs() を呼び出し、4つの結果の論理積(AND)を返す

メイン処理の流れ

• R を行列の行数、C を列数として取得する
• 答えを格納する変数 ans を 0 で初期化する
• すべてのセル (i, j) を走査し、matrix[i][j] が 1 であれば dfs(i, j) を呼び出す
• dfs の戻り値が True であれば、ans を 1 増やす
• 最終的に ans を返す

Pythonでの実装例

class Solution:
    def solve(self, matrix):
        def dfs(i, j):
            if i < 0 or j < 0 or i >= R or j >= C:
                return False
            if matrix[i][j] == 0:
                return True
            matrix[i][j] = 0
            a = dfs(i + 1, j)
            b = dfs(i - 1, j)
            c = dfs(i, j + 1)
            d = dfs(i, j - 1)
            return a and b and c and d

        R, C = len(matrix), len(matrix[0])
        ans = 0
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 1:
                    if dfs(i, j):
                        ans += 1
        return ans

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

入力

matrix = [
[1, 0, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0] ]

出力

2

計算量について

時間計算量は O(R×C) です。各セルは高々1回しか訪問されないためです。また、訪問済みのセルは 0 に書き換えてマークしているため、追加のメモリは再帰スタック分のみで済みます。空間計算量は最悪ケースで O(R×C) となります。

まとめ

このように、DFSを活用することで「完全に囲まれた島」の数をシンプルに数えることができます。通常の島の数え方との違いは、行列の端に到達した時点で False を返す点にあります。このテクニックは、LeetCodeの「Number of Closed Islands」など、類似の応用問題にも役立ちますので、ぜひマスターしておきましょう。