[Leetcode/파이썬] 130. Surrounded Regions

Surrounded Regions

---

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.
• Region: To form a region connect every 'O' cell.
• Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

 

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Explanation:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'.

 

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        n, m = len(board), len(board[0])

        v = [[0] * m for _ in range(n)]
        
        def dfs(si: int, sj: int) :
            v[si][sj] = 1
            
            for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
                ni, nj = si + di, sj + dj

                if 0 <= ni < n and 0 <= nj < m and v[ni][nj] == 0 and board[ni][nj] == 'O' :
                    dfs(ni, nj)
                
        for i in range(n) :
            if board[i][0] == 'O' :
                dfs(i, 0)
            if board[i][m-1] == 'O' :
                dfs(i, m-1)

        for j in range(m) :
            if board[0][j] == 'O' :
                dfs(0, j)
            if board[n-1][j] == 'O' :
                dfs(n-1, j)
        
        for i in range(n) :
            for j in range(m) :
                if board[i][j] == 'O' and v[i][j] == 0 :
                    board[i][j] = 'X'

일반적인 BFS, DFS 문제이지만, 이 문제를 정확하게 해결하는 데에는 실패하였다. DFS 함수를 구현이야 정석적인 구현이기 때문에 딱히 언급은 하지 않겠다. 

문제에서 X에 둘러쌓이지 않은 부분은 놔두고 둘러 쌓인 부분만 O를 X로 바꾸는 작업을 해야되는데, 이를 어떻게 판별하냐가 문제였다. 다르게 생각하면 각 테두리에 존재하는 O를 체크한 다음, 해당 O와 연결된 모든 노드를 체크한다. 그리고 O이면서, 방문하지 않은 노드들은 테두리와 연결되지 않은 노드들이기 때문에 X에 둘러 쌓였다고 판단할 수 있다. 이 단계를 생각하지 못했다.