Pythonで水に完全に囲まれた島をすべて削除するプログラムの実装方法

問題の概要

0と1だけで構成される二値行列を考えます。ここで1は陸地、0は水を表します。「島」とは、1が上下左右(斜めは含まない)に連なったグループのことです。この問題では、行列の外周(端)に一切接しておらず、水に完全に囲まれている島を見つけ出し、それらをすべて0(水)に変換します。

言い換えれば、「行列の端にたどり着ける陸地だけを残し、内部に孤立した島をすべて消す」ことが目的です。

入力例

出力例

中央にあった大きな島は外周に接していないためすべて0になり、一方で外周に接している四隅の陸地はそのまま残ります。

解法のアプローチ

この問題は幅優先探索(BFS)を使うと効率的に解けます。基本的な考え方は次のとおりです。

1. 探索の起点は行列の外周にあるセルだけに限定します。
2. 起点が陸地(1)なら、そこからBFSで到達できるすべての陸地を新しい行列Bに記録します。
3. Bに記録されなかった陸地は「外周に到達できない=水に完全に囲まれた島」なので、0のままになります。

具体的な手順

• row := 行列Aの行数
• col := 行列Aの列数
• B := Aと同じサイズの行列を用意し、すべて0で初期化
• seen := 訪問済みセルを管理するための空の集合(set)
• i を 0〜row-1、j を 0〜col-1 の範囲で二重ループ:
  • (i, j) が外周のセルでなければ次の反復へ
  • (i, j) がすでにseenに含まれていれば次の反復へ
  • A[i][j] が 0(水)なら次の反復へ
  • d := (i, j) を初期要素とする両端キュー(deque)
  • d が空でない間、以下を繰り返す:
    • (x, y) := d の左端から要素を取り出す
    • B[x][y] := 1 とする
    • (x, y) の上下左右の近傍 (x2, y2) のそれぞれについて、未訪問なら d の末尾に追加し、seen に登録する
• 最後に B を返す

Pythonでの実装例

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

from collections import deque

class Solution:
    def solve(self, A):
        row = len(A)
        col = len(A[0])
        B = [[0 for _ in range(col)] for _ in range(row)]
        seen = set()

        def nei(i, j):
            if i + 1 < row and A[i + 1][j]:
                yield (i + 1, j)
            if j + 1 < col and A[i][j + 1]:
                yield (i, j + 1)
            if i - 1 >= 0 and A[i - 1][j]:
                yield (i - 1, j)
            if j - 1 >= 0 and A[i][j - 1]:
                yield (i, j - 1)

        for i in range(row):
            for j in range(col):
                # 外周のセルのみを探索の起点にする
                if i not in (0, row - 1) and j not in (0, col - 1):
                    continue
                if (i, j) in seen:
                    continue
                if A[i][j] == 0:
                    continue
                d = deque([(i, j)])
                seen.add((i, j))
                while d:
                    x, y = d.popleft()
                    B[x][y] = 1
                    for x2, y2 in nei(x, y):
                        if (x2, y2) not in seen:
                            d.append((x2, y2))
                            seen.add((x2, y2))
        return B

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

入力

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

出力

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

計算量について

各セルは最大でも一度しかキューに追加されないため、時間計算量は O(row × col) です。また、結果を格納する行列Bと訪問管理用の集合が必要となるため、空間計算量も O(row × col) となります。行列全体を一度走査するだけで処理が完了する、非常に効率的な手法です。