Pythonで2Dグリッド（マトリックス）内の島の数を数えるアルゴリズム

2次元のバイナリマトリックス（0と1のみで構成されるグリッド）が与えられたとき、その中に存在する「島」の数を数える問題を考えてみましょう。

ここでいう島とは、水に囲まれた陸地の集合であり、隣接する陸地が水平方向または垂直方向につながって形成される領域のことです。斜め方向のつながりは島とはみなしません。また、グリッドの四辺はすべて水に囲まれているものと仮定します。

問題の例

例として、次のようなグリッドを考えてみます。

この場合、色分けしたように陸地（1）のかたまりが3つ存在するため、答えは 3 となります。

解き方のアプローチ

この問題は、DFS（深さ優先探索）を使うことで効率的に解けます。基本的な考え方は以下の通りです。

• グリッド全体を走査し、まだ訪れていない陸地（値が「1」のセル）を見つけたら、島の数を1つカウントします。
• そのセルからDFSを開始し、上下左右につながるすべての陸地を「水（0）」に変えていきます。これにより、同じ島を二重にカウントすることを防げます。
• 走査が終わった時点でのカウントが、島の総数となります。

アルゴリズムの手順

• メソッド numIslands() で島の数を数え、補助メソッド makeWater() でつながった陸地を水に変えます。
• グリッドの行数が0の場合は、0を返します。
• n = 行数、m = 列数、ans = 0 として初期化します。
• i を 0 から n-1 まで、j を 0 から m-1 までループします。
  • grid[i][j] == "1" の場合、ans を1増やします。
  • makeWater(i, j, n, m, grid) を呼び出して、その島全体を水に変えます。
• makeWater() はインデックス i, j、行数・列数 n, m、およびグリッドを受け取ります。
  • i < 0 または j < 0 または i >= n または j >= m の場合は、範囲外なので処理を終了します。
  • grid[i][j] が「0」（水）なら何もせず返します。そうでなければ grid[i][j] := "0" として水に変えます。
  • 再帰的に makeWater(i+1, j)、makeWater(i, j+1)、makeWater(i-1, j)、makeWater(i, j-1) を呼び出し、四方の隣接セルも処理します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0
        n = len(grid)
        m = len(grid[0])
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":
                    ans += 1
                self.make_water(i, j, n, m, grid)
        return ans

    def make_water(self, i, j, n, m, grid):
        if i < 0 or j < 0 or i >= n or j >= m:
            return
        if grid[i][j] == "0":
            return
        else:
            grid[i][j] = "0"
        self.make_water(i + 1, j, n, m, grid)
        self.make_water(i, j + 1, n, m, grid)
        self.make_water(i - 1, j, n, m, grid)
        self.make_water(i, j - 1, n, m, grid)

入力例

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

出力結果

3

計算量について

このアルゴリズムでは、各セルは高々一度しか訪問されないため、時間計算量は O(n × m)（nは行数、mは列数）となります。ただし、再帰によるDFSを使用しているため、島が大きい場合には再帰の深さが最大 O(n × m) まで達する可能性があり、Pythonのデフォルトの再帰上限（通常1000）に注意が必要です。大きな入力に対しては、スタックオーバーフローを避けるために反復的なBFS（幅優先探索）や、明示的なスタックを使ったDFSへの書き換えも検討するとよいでしょう。