Pythonで島の数を数える方法｜DFSによるグリッド探索アルゴリズム

問題の概要

0と1で構成された2次元グリッドが与えられ、そこに含まれる島の数を数えることを考えます。ここでいう「島」とは、水に囲まれた領域のうち、隣接する陸地（1）が水平方向または垂直方向につながって形成されるものを指します。グリッドの四方の端はすべて水に囲まれているものと仮定します。

たとえば、次のようなグリッドを考えてみましょう。色のついたセルは、それぞれ異なる島を表しています。

この場合、島は3つ存在することになります。

解き方のアプローチ

この問題は、DFS（深さ優先探索）を応用した「洪水フィル（Flood Fill）」の手法で効率よく解くことができます。使用するのは次の2つのメソッドです。

• numIslands()：島の総数をカウントするメソッド
• makeWater()：陸地を見つけたら、そこにつながる陸地をすべて「水（0）」に置き換えていくメソッド

アルゴリズムの手順

1. グリッドの行数が0の場合は、0を返します。
2. n＝行数、m＝列数、答えとなる ans＝0 として初期化します。
3. i を 0～n−1、j を 0～m−1 の範囲で二重ループを回します。
   • grid[i][j] が「1」であれば、ans に +1 します。
   • makeWater(i, j, n, m, grid) を呼び出し、その地点からつながる陸地をすべて水に変えます。
4. 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, …) を再帰的に呼び出します（実際の実装では上下左右の4方向すべてを探索します）。

以下の実装例を見ると、より理解が深まるでしょう。

サンプルコード

class Solution(object):
    def numIslands(self, grid):
        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)

ob1 = Solution()
print(ob1.numIslands([["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]]))

入力

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

出力

3

このように、陸地（1）を発見するたびに、そこから到達できる陸地全体を水に変えてしまうことで、同じ島を重複してカウントすることなく、正確に島の総数を求めることができます。