Pythonで2次元バイナリ行列から異なる島の形状を検出するプログラム

問題の概要

2次元のバイナリ行列が与えられ、その中に存在する「異なる島」の数を求めることを考えます。ここで、1 は陸地、0 は水を表します。島とは、上下左右に隣接した 1 の集合であり、その周囲がすべて水に囲まれている領域のことです。そして、2つの島は形状が異なる場合にのみ「一意（ユニーク）」であるとみなされます。

たとえば、入力が以下のような行列だったとします。

この場合、出力は 4 になります（異なる島はそれぞれ別の色で表されています）。

解法のアプローチ

この問題は、深さ優先探索（DFS）を使って各島のセルをすべて訪問し、その形状を「相対座標」として記録することで解けます。各島の基準点（探索開始セル）からのオフセット (i − k, j − l) を保存すれば、行列上の位置が違っても同じ形の島は必ず同じシグネチャを持つことになります。あとは集合（set）で重複判定を行うだけで、ユニークな島の個数を数えられます。

具体的な手順は以下の通りです。

• 関数 dfs(i, j, k, l) を定義します。i, j は現在のセルの座標、k, l は島の基準点の座標です。

• mat[i][j] を 0 に設定します（訪問済みマーク）。

• shape の末尾にペア (i − k, j − l) を追加します。

• i + 1 が mat の行数未満で、かつ mat[i + 1][j] が 1 の場合、dfs(i + 1, j, k, l) を呼び出します。

• j + 1 が mat の列数未満で、かつ mat[i][j + 1] が 1 の場合、dfs(i, j + 1, k, l) を呼び出します。

• i − 1 が 0 以上で、かつ mat[i − 1][j] が 1 の場合、dfs(i − 1, j, k, l) を呼び出します。

• j − 1 が 0 以上で、かつ mat[i][j − 1] が 1 の場合、dfs(i, j − 1, k, l) を呼び出します。

メイン処理では以下を実行します。

• cnt を 0 に初期化します。

• shapes を空の集合（set）として作成します。

• i を 0 から mat の行数までループさせます。

  • j を 0 から mat の列数までループさせます。

    • mat[i][j] が 1 の場合：

      • shape を空のリストとして作成します。

      • dfs(i, j, i, j) を呼び出して島全体を探索します。

      • shape をタプルに変換し、shapes に存在しない場合は cnt を 1 増やします。

      • shape を shapes に追加します。

• 最後に cnt を返します。

実装例

理解を深めるために、以下の Python 実装を見てみましょう。

class Solution:
   def solve(self, mat):
      def dfs(i, j, k, l):
         mat[i][j] = 0
         shape.append((i - k, j - l))
         if i + 1 < len(mat) and mat[i + 1][j]:
            dfs(i + 1, j, k, l)
         if j + 1 < len(mat[0]) and mat[i][j + 1]:
            dfs(i, j + 1, k, l)
         if i - 1 >= 0 and mat[i - 1][j]:
            dfs(i - 1, j, k, l)
         if j - 1 >= 0 and mat[i][j - 1]:
            dfs(i, j - 1, k, l)
      cnt = 0
      shapes = set()
      for i in range(len(mat)):
         for j in range(len(mat[0])):
            if mat[i][j]:
               shape = []
               dfs(i, j, i, j)
               shape = tuple(shape)
               if shape not in shapes:
                  cnt += 1
                  shapes.add(shape)
      return cnt
ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 1, 1, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0],
   [1, 1, 0, 1, 1]
]
print(ob.solve(matrix))

入力

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

出力

4

計算量の目安

時間計算量は O(行数 × 列数) です。各セルは訪問時に 0 に書き換えられるため、二度と探索されることはありません。また、島の形状はタプルとしてハッシュ化されるため、集合との比較も効率的に行えます。空間計算量も同様に O(行数 × 列数) となり、再帰スタックと shape の保存に依存します。