Pythonで2つのマップに重複して存在する島の数をカウントする方法

2つのバイナリ行列 mat1 と mat2 が与えられたとします。ここで、1は陸地を、0は水を表します。水に囲まれた1(陸地)の集まりは「島」と呼ばれます。この問題では、mat1とmat2の両方において、まったく同じ座標に存在する島の数を求める必要があります。

問題の例

たとえば、入力が次のような場合を考えてみましょう。

mat1:

mat2:

この場合の出力は 2 になります。重複している島は以下のようにハイライトされた部分です。

つまり、両方のマップで同じ座標に存在する島は2つあるということになります。

解決のためのアルゴリズム

この問題は、次の手順で解くことができます。

• r := mat1 の行数
• c := mat1 の列数
• last_row := r - 1
• last_col := c - 1
• 関数 mark(i, j) を定義します。この関数は以下の処理を行います。
  • mat1[i][j] := 0
  • mat2[i][j] := 0
  • i が0以外で、かつ mat1[i-1][j] または mat2[i-1][j] のどちらかが0以外の場合 → mark(i - 1, j) を呼び出す
  • j が0以外で、かつ mat1[i][j-1] または mat2[i][j-1] のどちらかが0以外の場合 → mark(i, j - 1) を呼び出す
  • j < last_col で、かつ mat1[i][j+1] または mat2[i][j+1] のどちらかが0以外の場合 → mark(i, j + 1) を呼び出す
  • i < last_row で、かつ mat1[i+1][j] または mat2[i+1][j] のどちらかが0以外の場合 → mark(i + 1, j) を呼び出す
• メイン処理では、まず不一致セルの除去を行います。
  • i を 0 から r - 1 まで繰り返す
    • j を 0 から c - 1 まで繰り返す
      • mat1[i][j] と mat2[i][j] が異なる場合 → mark(i, j) を呼び出す
• islands := 0 と初期化します。
• 再度 i を 0 から r - 1 まで繰り返す
  • j を 0 から c - 1 まで繰り返す
    • mat1[i][j] が0以外の場合
      • islands := islands + 1
      • mark(i, j) を呼び出す
• islands を返す

アルゴリズムのポイント

このアプローチの鍵となるのは、mark() 関数が両方のマップに対して同時にDFS(深さ優先探索)を実行する点です。まず、片方のマップにだけ島がある座標(値が一致しないセル)をすべて消去することで、残った陸地は必ず両方のマップで同じ形状・同じ位置に存在する島になります。その後、残った島を数えるだけで、重複する島の総数が得られます。

実装例

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

def solve(mat1, mat2):
    r = len(mat1)
    c = len(mat1[0])
    last_row = r - 1
    last_col = c - 1

    def mark(i, j):
        mat1[i][j] = mat2[i][j] = 0
        if i and (mat1[i - 1][j] or mat2[i - 1][j]):
            mark(i - 1, j)
        if j and (mat1[i][j - 1] or mat2[i][j - 1]):
            mark(i, j - 1)
        if j < last_col and (mat1[i][j + 1] or mat2[i][j + 1]):
            mark(i, j + 1)
        if i < last_row and (mat1[i + 1][j] or mat2[i + 1][j]):
            mark(i + 1, j)

    for i in range(r):
        for j in range(c):
            if mat1[i][j] != mat2[i][j]:
                mark(i, j)

    islands = 0
    for i in range(r):
        for j in range(c):
            if mat1[i][j]:
                islands += 1
                mark(i, j)
    return islands

mat1 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
mat2 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]
print(solve(mat1, mat2))

入力

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

出力

2

まとめ

この手法を使えば、2つのマップを同時に走査しながら重複する島だけを効率的に特定できます。計算量は各セルを最大2回訪問するため O(r × c) となり、マップのサイズに対して線形時間で処理が完了します。再帰によるDFSの実装はシンプルですが、非常に大きなマップを扱う場合は再帰深度の制限に注意し、必要に応じてスタックベースの反復処理に置き換えるとよいでしょう。