Pythonで行列（グリッド）から最大の島の面積を求めるプログラム

問題の概要

0と1のみで構成された2値行列を考えてみましょう。ここでは「1」が陸地、「0」が水を表しており、島とは水に囲まれた隣接する1の集まりを指します。行列の外側（端）もすべて水に囲まれているものと仮定し、その中で最も大きな島の面積（セルの数）を求めるのが今回の課題です。

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

この場合、最大の島は2〜3行目にまたがる6個の連結したセルで構成されているため、出力は6となります。

解法のアプローチ：DFS（深さ優先探索）

この問題は、DFS（Depth First Search：深さ優先探索）を用いることで効率的に解けます。基本的な考え方は、陸地のセルを見つけたらそこから上下左右へ探索を広げ、連結した1をすべて数え上げるというものです。まず、dfs()関数を定義します。引数にはmatrix（行列）、r（行インデックス）、c（列インデックス）を受け取ります。

• totalを1増やし、訪問済みであることを示すためにmatrix[r][c]を0に設定します。
• 上方向：r - 1 >= 0 かつ matrix[r - 1][c] が 1 の場合、dfs(matrix, r - 1, c) を呼び出します。
• 左方向：c - 1 >= 0 かつ matrix[r][c - 1] が 1 の場合、dfs(matrix, r, c - 1) を呼び出します。
• 下方向：r + 1 < 行数 かつ matrix[r + 1][c] が 1 の場合、dfs(matrix, r + 1, c) を呼び出します。
• 右方向：c + 1 < 列数 かつ matrix[r][c + 1] が 1 の場合、dfs(matrix, r, c + 1) を呼び出します。

続いて、メイン処理では以下の手順を実行します。

• r_len（行数）と c_len（列数）を取得し、max_island を 0 で初期化します。
• すべてのセルを走査し、matrix[r][c] が 1 のセルを見つけたら、total をリセットして dfs() を呼び出します。
• 探索終了後、max_island を max(max_island, total) で更新し、全セルの走査が完了したら max_island を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

class Solution:
   def solve(self, matrix):
      self.r_len = len(matrix)
      self.c_len = len(matrix[0])
      max_island = 0
      for r in range(self.r_len):
         for c in range(self.c_len):
            if matrix[r][c] == 1:
               self.total = 0
               self.dfs(matrix, r, c)
               max_island = max(max_island, self.total)
      return max_island
   def dfs(self, matrix, r, c):
      self.total += 1
      matrix[r][c] = 0
      if r - 1 >= 0 and matrix[r - 1][c] == 1:
         self.dfs(matrix, r - 1, c)
      if c - 1 >= 0 and matrix[r][c - 1] == 1:
         self.dfs(matrix, r, c - 1)
      if r + 1 < self.r_len and matrix[r + 1][c] == 1:
         self.dfs(matrix, r + 1, c)
      if c + 1 < self.c_len and matrix[r][c + 1] == 1:
         self.dfs(matrix, r, c + 1)
ob = Solution()
matrix = [ [0, 0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0] ]
print(ob.solve(matrix))

入力

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

出力

6