Pythonで解く「囲まれた領域（Surrounded Regions）」問題：DFSを使った効率的な解法

問題の概要

XとOで構成された2次元ボードが与えられます。この中から、Xによって四方を完全に囲まれたOの領域をすべて「捕捉」します。捕捉とは、その囲まれた領域内のOをすべてXへ置き換えることを指します。

注意すべき点として、ボードの外周（端）に接しているOはボードの外側とつながっているため「囲まれていない」とみなされ、変換の対象外になります。

入力ボードの例

処理後の出力

中央付近のOはXに完全に囲まれているため、すべてXへ変換されます。一方、下端にあるOはボードの境界に接しているため、そのままOとして残ります。

解法の考え方

各Oについて「Xに完全に囲まれているか」を個別に判定しようとすると、計算コストが非常に高くなります。そこで発想を逆転させ、ボードの端に位置するOから探索を開始し、そこからたどり着けるOをすべてマークします。境界から到達可能なOは決して捕捉されないためです。

マークには仮の文字「1」を使用します。すべてのマーク処理が完了した後、次の変換を行います。

• 残っている「O」→ 囲まれた領域なので「X」へ変換
• マーク済みの「1」→ 元の「O」へ復元

アルゴリズムの手順

1. ボードが空の場合は、そのまま空のボードを返します。
2. 各行iについて、左端board[i][0]および右端board[i][最終列]が「O」であれば、それぞれmake_one(board, i, 0)、make_one(board, i, 最終列)を呼び出します。
3. 各列jについて、上端board[0][j]および下端board[最終行][j]が「O」であれば、それぞれmake_one(board, 0, j)、make_one(board, 最終行, j)を呼び出します。
4. ボード全体を走査し、「O」は「X」に、「1」は「O」に変換します。

make_one関数の動作（深さ優先探索）

• i < 0、j < 0、i ≥ 行数、j ≥ 列数のいずれかに該当する場合、またはboard[i][j]が「X」もしくは「1」である場合は、何もせずに戻ります。
• board[i][j]を「1」に設定します。
• 上下左右の4方向（(i+1, j)、(i−1, j)、(i, j+1)、(i, j−1)）に対して再帰的にmake_oneを呼び出します。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        if not board:
            return board
        for i in range(len(board)):
            if board[i][0]=='O':
                self.make_one(board,i,0)
            if board[i][len(board[0])-1] == 'O':
                self.make_one(board,i,len(board[0])-1)
        for i in range(len(board[0])):
            if board[0][i]=='O':
                self.make_one(board,0,i)
            if board[len(board)-1][i] == 'O':
                self.make_one(board,len(board)-1,i)
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j]=='O':
                    board[i][j]='X'
                elif board[i][j]=='1':
                    board[i][j]='O'
    def make_one(self, board,i,j):
        if i<0 or j<0 or i>=len(board) or j>=len(board[0]) or board[i][j]=='X' or board[i][j]=='1':
            return
        board[i][j]='1'
        self.make_one(board,i+1,j)
        self.make_one(board,i-1,j)
        self.make_one(board,i,j+1)
        self.make_one(board,i,j-1)

計算量

時間計算量・空間計算量はともにO(m × n)（m：行数、n：列数）です。各セルは高々一度しか訪問されないため、ボード全体を線形時間で効率的に処理できます。

入力

[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

出力

[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]