[LeetCode] 130. Surrounded Regions

130. Surrounded Regions

Medium

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

 

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: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

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'.

---

문제 풀이

• 2차원 배열이 주어진다. 
• 2차원 배열에는 X, O가 들어있다. 
• X로 둘러쌓인 O를 X로 뒤집어야한다.
• 하지만 O가 경계에 닿아있다면 그 O에 이어져있는 O들은 뒤집지 않아도 된다. 
• 즉 경계에 있는 O가 붙어있지 않으면 모두 O를 X로 뒤집어주면되는 것이다. 
• 완전 탐색을 해야하는데, 제한 사항을 보면 2차원 배열의 최대 길이가 각각 200이다. 
• 하지만 문제를 이해해보면 O들만 확인해보면되서 BFS로도 풀 수 있다. 
• O의 좌표를 모두 저장하고, BFS를 각각 돌리면서 현재 O위치의 좌표를 모두 임시 저장한다.
• flag를 정해서 이어진 O가 경계에 닿아있다면 1로 바꿔준다.
• 경계에 닿아있는 O가 한개도 없다면 2차원 배열에는 O 혹은 X 밖에 없기 때문에, O를 X로 뒤집어줘야한다.

소스 코드

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        dr = [[0, 1], [1, 0], [-1, 0], [0, -1]]
        que = []
        o_lst = []
        visited = set()
        n, m = len(board), len(board[0])
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O':
                    o_lst.append((i, j))
        
        for node in o_lst:
            if node in visited: continue
            visited.add(node)
            que.append(node)
            flag = 0
            temp = []
            temp.append(node)
            while que:
                cur_node = que.pop(0)
                cur_y = cur_node[0]
                cur_x = cur_node[1]
                for op_y, op_x in dr:
                    nxt_y = cur_y + op_y
                    nxt_x = cur_x + op_x
                    if nxt_y < 0 or nxt_x < 0 or nxt_y >= n or nxt_x >= m:
                        flag = 1
                        continue
                    if (nxt_y, nxt_x) in visited: continue
                    if board[nxt_y][nxt_x] == 'O':
                        temp.append((nxt_y, nxt_x))
                        visited.add((nxt_y, nxt_x))
                        que.append((nxt_y, nxt_x))
            if flag == 0:
                for ty, tx in temp:
                    board[ty][tx] = 'X'