LeetCode: 130. Surrounded Regions

고립된 O를 X로 만드는 문제이다.

"고립된"은 board의 경계와 이어지지 않는 O들이다.

고로 경계의 O와 이어진 O들을 제외하고, 모두 X 처리해준다.

from collections import deque
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        dy = [0, 1, 0, -1]
        dx = [1, 0, -1, 0]
        
        island = set()
        
        m, n = len(board), len(board[0])
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    island.add((i, j))
        
        visited = set()
        for i in range(m):
            for j in range(n):
                # edge
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    if board[i][j] == "O":
                        # if not visited
                        if (i, j) not in visited:
                            # bfs to find non_island
                            q = deque()
                            q.append((i, j))
                            visited.add((i, j))
                            while q:
                                now = q.popleft()
                                island.discard(now)
                                for d in range(4):
                                    next_y = now[0] + dy[d]
                                    next_x = now[1] + dx[d]
                                    if 0 <= next_y <= m - 1 and 0 <= next_x <= n - 1:
                                        if (next_y, next_x) not in visited and \
                                        board[next_y][next_x] == "O":
                                            q.append((next_y, next_x))
                                            visited.add((next_y, next_x))
        
        for coord in island:
            board[coord[0]][coord[1]] = "X"