[LeetCode] 130. Surrounded Regions (Python) 풀이

문제 요구사항 

• "O" 를 "X"로 flip 하라. 
• 단, 가장 자리에 맞닿은 "O"의 경우 뒤집으면 안되며, 이 가장자리와 인접한 다른 "O"의 경우에도 뒤집지 않는다. 

풀이 방법 (알고리즘 : BFS)

• 우선 M*N 배열에서 "O" 가 있는 칸의 위치 (i, j) 를 구한다. -> island 집합에 저장
• 가장자리에 있는 "O" 를 찾아서, "O"와 인접한 칸들까지 BFS로 찾아서 island 라는 집합에서 빼준다. 
• 남아있는 좌표들은 X 로 flip 이 가능한 위치이므로 모두 변환해 준다. 

from collections import deque

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        N = len(board[0])
        M = len(board)

        island = set()  # O 를 섬으로 취급

        # 내부에 있는 O 확인하기
        for i in range(M):
            for j in range(N):
                if board[i][j] == "O":
                    island.add((i, j))

        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        # BFS

        def bfs(x, y):
            queue = deque([])
            queue.append((x, y))
            visited[x][y] = True
            while queue:
                x, y = queue.popleft()
                island.discard((x, y))  # 가장자리는 X 처리에서 제외 필요함
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < M and 0 <= ny < N and board[nx][ny] == "O" and not visited[nx][ny]:
                        queue.append((nx, ny))
                        visited[nx][ny] = True

        visited = [[False] * N for _ in range(M)]
        for i in range(M):
            for j in range(N):
                if (i == M - 1 or i == 0 or j == N - 1 or j == 0):
                    if not visited[i][j] and board[i][j] == "O":
                        print(i, j)
                        bfs(i, j)

        # O -> X flip
        for x, y in island:
            board[x][y] = "X"