a-084-surrounded-regions2026-08-11mediumleetcode #130neetcode150

둘러싸인 영역

#array#depth-first-search#breadth-first-search#union-find#matrix

↗ leetcode #130 · a-084-surrounded-regions

문제

· problem

P.a-084-surrounded-regions

둘러싸인 영역

m x n 행렬 board가 주어지며, 이 행렬은 'X'와 'O' 문자를 포함합니다. 다음과 같이 정의되는 둘러싸인 영역을 포획하세요: 연결(Connect): 셀은 수평 또는 수직으로 인접한 셀과 연결됩니다. 영역(Region): 영역을 형성하려면 모든 'O' 셀을 연결해야 합니다. 포위(Surround): 영역이 포위되면 그 영역의 어떤 'O' 셀도 보드의 경계에 있지 않습니다. 이러한 영역은 'X' 셀로 완전히 둘러싸여 있습니다. 둘러싸인 영역을 포획하려면 원래 보드에서 모든 'O'를 'X'로 바꾸세요. 함수는 아무것도 반환할 필요가 없습니다.

제약

· 1 ≤ m, n ≤ 200
· board[i][j] is 'X' or 'O'
· Modification must be in-place

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

example 2input → output

[["X"]]

[["X"]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
어떤 조건이 영역을 '포위'되었다고 판단하나요?
☐
대각선 연결이 'O' 영역 형성에 포함되나요?
☐
'O' 셀이 보드 경계에 닿으면 그 영역을 포획할 수 있나요?
☐
원본 board를 수정하지 않고 새로운 board를 반환해야 하나요?
☐
전체 board가 'O'로만 이루어지면 어떻게 되나요?
☐
영역의 모든 셀을 한 번에 방문하지 않고 개별적으로 검사하면 어떻게 되나요?
☐
DFS와 BFS 중 어느 것이 이 문제에 더 적합한가요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 방문 추적 집합 초기화

○

flag = set()

○

flag = []

○

flag = [[False] * cols for _ in range(rows)]

step 2· 재귀 함수의 경계 조건 확인│ 중첩

○

if not(r in range(rows) and c in range(cols)) or board[r][c] != 'O' or (r, c) in flag:

○

if board[r][c] != 'O' or (r, c) in flag:

○

if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] == 'X':

step 3· 현재 셀을 방문 집합에 추가│ │ 중첩

○

flag.add((r, c))

○

board[r][c] = '#'

○

visited[r * cols + c] = True

step 4· 경계에서 경계 'O' 찾기│ 중첩

○

if( (r == 0 or c == 0 or r == rows - 1 or c == cols - 1) and board[r][c] == 'O'):

○

if (r == 0 or r == rows - 1) and board[r][c] == 'O':

○

if (r == 0 and c == 0) and board[r][c] == 'O':

step 5· 포위된 'O' 셀 식별 및 변환│ │ 중첩

○

if board[r][c] == 'O' and (r, c) not in flag:

○

if board[r][c] == 'O':

○

if (r, c) not in flag:

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def solve(self, board: List[List[str]]) -> None:

        rows, cols = len(board), len(board[0])

        flag = set()

        def dfs(r, c):

            if not(r in range(rows) and c in range(cols)) or board[r][c] != 'O' or (r, c) in flag:

                return

            flag.add((r, c))

            return (dfs(r + 1, c), dfs(r - 1, c), dfs(r, c + 1), dfs(r, c - 1))

        # traverse through the board

        for r in range(rows):

            for c in range(cols):

                if( (r == 0 or c == 0 or r == rows - 1 or c == cols - 1) and board[r][c] == 'O'):

                    dfs(r, c)

        # set all of the 'X's to 'O's

        for r in range(rows):

            for c in range(cols):

                if board[r][c] == 'O' and (r, c) not in flag:

                    board[r][c] = 'X'

'''

    def solve(self, board: List[List[str]]) -> None:

        ROWS, COLS = len(board), len(board[0])

        def capture(r, c):

            if r < 0 or c < 0 or r == ROWS or c == COLS or board[r][c] != "O":

                return

            board[r][c] = "T"

            capture(r + 1, c)

            capture(r - 1, c)

            capture(r, c + 1)

            capture(r, c - 1)

        # 1. (DFS) Capture unsurrounded regions (O -> T)

        for r in range(ROWS):

            for c in range(COLS):

                if board[r][c] == "O" and (r in [0, ROWS - 1] or c in [0, COLS - 1]):

                    capture(r, c)

        # 2. Capture surrounded regions (O -> X)

        for r in range(ROWS):

            for c in range(COLS):

                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"

'''

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

→

[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

case 2

[["X"]]

→

[["X"]]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.