Pythonで2次元行列内の島の数を数える方法｜DFSを使った実装を解説

問題の概要

0と1だけで構成される2次元のバイナリ行列が与えられ、その中に存在する「島」の数を求めるのがこの問題です。ここでは1を陸地、0を水とみなし、上下左右に隣接した1の集まり(斜め方向の隣接は考慮しない)で、周囲を水に囲まれた領域を1つの島としてカウントします。

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

この場合、島は4つ存在するため、出力は4となります。

解き方のアプローチ(深さ優先探索：DFS)

この問題は、グラフ探索アルゴリズムのひとつである深さ優先探索(DFS)を使うことで効率的に解けます。全体の流れは以下の通りです。

1. explore()関数を定義する

explore()関数は、行(row)、列(col)、行列(matrix)を引数として受け取ります。

• rowまたはcolが行列の範囲外にある、もしくはmatrix[row][col]が0の場合は、何もせずに処理を終了します。
• 該当セルの値を0に書き換えます。これは、一度訪れた陸地を水に変えることで、同じ島を二重にカウントしないための「訪問済み」マークの役割を果たします。
• 上下左右の4方向それぞれに対して、再帰的にexplore()を呼び出します。

2. メイン処理(solve())を実装する

• 行列が空の場合は0を返します。
• 島の数を格納する変数islandsを0で初期化します。
• 行列の全セルを二重ループで走査し、値が1のセルを見つけたらislandsを1増やし、そのセルを起点にexplore()を呼び出して、つながっている陸地をすべて0に置き換えます。
• 走査が完了したらislandsを返します。

Pythonでの実装例

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

class Solution:
    def explore(self, row, col, matrix):
        if (
            row < 0 or col < 0
            or row > len(matrix) - 1
            or col > len(matrix[0]) - 1
            or matrix[row][col] == 0
        ):
            return
        matrix[row][col] = 0
        self.explore(row + 1, col, matrix)
        self.explore(row - 1, col, matrix)
        self.explore(row, col + 1, matrix)
        self.explore(row, col - 1, matrix)

    def solve(self, matrix):
        if not matrix:
            return 0
        islands = 0
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] == 1:
                    islands += 1
                    self.explore(row, col, matrix)
        return islands


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

入力

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

出力

4

計算量について

このアルゴリズムでは、各セルは高々1回しか訪問されません。そのため、時間計算量はO(行数 × 列数)となります。また、最悪の場合(行列全体が陸地の場合など)には再帰呼び出しが行列のセル数と同じ深さまで及ぶ可能性があるため、空間計算量もO(行数 × 列数)と考えられます。