Graphs: 130. Surrounded Regions★★

130. Surrounded Regions

 

이 문제에서는 주어진 m × n 크기의 보드에서 O로 이루어진 영역이 X로 둘러싸여 있는 경우,

==> 해당 영역의 모든 O를 X로 바꾸는 것입니다.

다만, 보드의 가장자리와 연결된 O는 둘러싸인 영역으로 간주하지 않으며 그대로 유지합니다.

---

문제를 해결하기 위한 접근 방식

1. 가장자리와 연결된 O를 찾기:
   • 보드의 가장자리에서 시작하여, O로 이루어진 영역을 탐색하고, 해당 영역을 방문 처리합니다.
   • 이 과정에서 가장자리와 연결된 O는 둘러싸이지 않은 영역임을 표시합니다.
2. O를 X로 바꾸기:
   • 보드 전체를 순회하며, 방문되지 않은 O는 둘러싸인 영역이므로 X로 바꿉니다.
   • 방문된 O는 가장자리와 연결된 영역이므로 그대로 유지합니다.
3. 탐색 방식:
   • DFS나 BFS를 사용하여 O로 이루어진 영역을 탐색합니다.
   • 방문된 O는 임시로 다른 값(예: 'T')으로 표시해 나중에 구분합니다.

 

https://youtu.be/9z2BunfoZ5Y?si=BOyYlfYO2t3Sao5t

 

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

        def bfs_capture(r, c): # 이번 bfs는 큐가 아니라 재귀로. 
            # 좌표값이 유효한 영역이 아니거나, 보드의 문자가 "O" 이 아니면
            if ((r < 0 or c < 0 or r == rows or c == cols) or
                (board[r][c] != "O")):
                return 

            board[r][c] = "T" # "O" 를 "T"로 바꿔주고
            bfs_capture(r+1, c)
            bfs_capture(r-1, c)
            bfs_capture(r, c+1)
            bfs_capture(r, c-1)

        # 1. Capture unsurrounded regions (O->T)
        #    박스의 경계선 영역은 unsurrounded 영역임
        for r in range(rows):
            for c in range(cols):
                if (board[r][c] == "O" and # Capture 영역이고
                    (r in [0, rows-1] or c in [0, cols-1])): # 박스 경계선에 있으면
                    bfs_capture(r, c)        

        # 2. Capture surrounded region (O->X)        
        for r in range(rows):
            for c in range(cols):
                # 이미 unsurrounded 영역에 있는 "O"는 "T"로 바뀐 상태여서 "X"로 바꿔도 됨
                if board[r][c] == "O": 
                    board[r][c] = "X" 

        # 3. Uncapture unsurrounded regions (T->O)
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == "T": 
                    board[r][c] = "O"

 

DFS로 풀이(최종 내 코드)

 

from typing import List

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # 4방향 검색
        # 4-directional search: Up, Down, Left, Right
        # O 영역이 X로 둘러싸여 있으면, O -> X 로 바꿈
        # If a region of 'O' is completely surrounded by 'X', convert 'O' to 'X'.
        # 단, edge와 닿여 있으면 X로 변경하지 않음.
        # However, if the 'O' is connected to the edge, do not convert it to 'X'.

        ROWS, COLS = len(board), len(board[0])  # 행과 열의 크기 / Dimensions of rows and columns

        def dfs(r, c):
            """
            가장자리와 연결된 'O'를 탐색하여 임시로 'T'로 바꿈
            Explore all 'O' connected to the edge and temporarily mark them as 'T'.
            """
            if r in range(ROWS) and c in range(COLS) and board[r][c] == "O":
                board[r][c] = "T"  # 임시로 'T'로 표시 / Mark as 'T' temporarily
                # 네 방향으로 이동하며 DFS 호출 / Call DFS in four directions
                dfs(r + 1, c)  # 아래로 / Down
                dfs(r - 1, c)  # 위로 / Up
                dfs(r, c + 1)  # 오른쪽으로 / Right
                dfs(r, c - 1)  # 왼쪽으로 / Left

        # 1. 가장자리에 있는 'O'에서 DFS 시작
        # Start DFS from 'O' cells on the edges
        for r in range(ROWS):
            for c in [0, COLS - 1]:  # 왼쪽 및 오른쪽 가장자리 / Left and right edges
                if board[r][c] == "O":
                    dfs(r, c)

        for r in [0, ROWS - 1]:  # 위쪽 및 아래쪽 가장자리 / Top and bottom edges
            for c in range(COLS):
                if board[r][c] == "O":
                    dfs(r, c)

        # 2. 보드 전체를 순회하며 'O'와 'T' 처리
        # Traverse the board to process 'O' and 'T'
        for r in range(ROWS):
            for c in range(COLS):
                if board[r][c] == "O":  
                    # 'T'로 바뀌지 않은 'O'는 둘러싸인 영역이므로 'X'로 변경
                    # If 'O' is not changed to 'T', it is surrounded and converted to 'X'
                    board[r][c] = "X"
                elif board[r][c] == "T":
                    # 'T'로 바뀐 것은 가장자리와 연결된 영역이므로 다시 'O'로 복구
                    # If marked as 'T', it is connected to the edge and restored to 'O'
                    board[r][c] = "O"