LeetCode

LeetCode 130 Surrounded Regions 풀이: 경계 연결 영역을 보존하는 BFS

2026년 9월 18일

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

문제: 130. Surrounded Regions
출처: LeetCode
자체 판단 난이도: Level 3

격자 안의 O 영역을 바로 뒤집으면 경계에 연결되어 보존해야 하는 영역까지 바꿀 수 있다. 경계에서 시작해 연결된 영역을 먼저 구분하고 남은 영역만 처리해야 하므로 그래프 탐색과 제자리 상태 변경에 대한 이해가 필요해 Level 3으로 판단했다.

1. 문제 요약

X와 O로 이루어진 board가 주어진다. 상하좌우로 연결된 O 영역 중 보드의 가장자리와 연결되지 않은 영역은 모두 X로 바꾼다. 가장자리에 닿아 있거나 가장자리의 O와 연결된 영역은 외부로 이어져 있으므로 그대로 둔다.

문제의 조건은 다음과 같다.

행과 열의 크기는 각각 1 이상 200 이하다.
각 칸은 X 또는 O다.
연결은 상하좌우 방향만 허용된다.
결과는 반환하지 않고 입력 board를 제자리에서 수정한다.
가장자리의 O와 연결된 모든 O는 보존해야 한다.

내부에 있는 O라도 아래쪽 가장자리의 O와 상하좌우로 이어져 있다면 둘 다 뒤집으면 안 된다. 영역의 모양이나 크기보다 경계와 연결되어 있는지가 핵심 조건이다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

그래프 구조와 방문 기록

각 칸을 그래프의 노드로 생각하고, 상하좌우로 인접한 칸을 간선으로 본다. 이때 목표는 모든 O 영역을 찾는 것이 아니라, 경계의 O에서 도달할 수 있는 O를 보존하는 것이다.

탐색 중인 안전한 O를 임시 문자 T로 바꾸어 방문 기록과 보존 표시를 동시에 처리한다. 마지막 전체 순회에서는 다음 규칙을 적용한다.

아직 O인 칸: 경계에서 도달할 수 없으므로 X로 변경
임시 T인 칸: 경계와 연결된 안전한 영역이므로 O로 복원

상태 전이와 경계 처리

첫 행, 마지막 행, 첫 열, 마지막 열에서 O인 칸을 큐에 넣고 T로 표시한다.
큐에서 칸을 하나 꺼내 상하좌우 이웃을 확인한다.
이웃이 범위 안에 있고 아직 O라면 T로 바꾼 뒤 큐에 넣는다.
경계에서 연결된 모든 칸을 표시한 뒤 보드 전체를 순회한다.
남은 O를 X로 바꾸고 T를 O로 되돌린다.

경계 칸은 모서리에서 중복으로 확인될 수 있지만, 큐에 넣는 순간 T로 변경하므로 같은 칸이 여러 번 탐색되지 않는다. 행이나 열의 크기가 1인 경우 모든 칸이 경계에 있으므로 O가 보존되고, 이 방식은 별도 예외 처리 없이 그대로 동작한다.

경계와 연결된 O만 보존하는 이유

“둘러싸인 영역을 찾는다”는 조건을 직접 검사하는 것보다 “절대 뒤집으면 안 되는 영역을 먼저 찾는다”가 쉽다. 경계에 있는 O는 보드 밖으로 연결되어 있으므로 안전하고, 그 안전한 칸에서 BFS를 확장하면 보존해야 하는 모든 O를 얻을 수 있다.

탐색이 끝난 뒤에도 O로 남은 칸은 어떤 경계 O에서도 도달하지 못한 칸이다. 그 칸들은 반드시 X로 바꿔도 된다. 임시 문자 하나만 사용하면 별도 visited 배열 없이 보드 자체에 탐색 상태를 기록할 수 있다.

시간·공간 복잡도

각 칸은 경계 탐색과 BFS, 마지막 변환 과정에서 일정한 횟수만 확인된다. 행을 m, 열을 n이라고 하면 시간 복잡도는 O(mn)이다. 보드 자체를 방문 표시와 결과 저장에 재사용하고, 큐에 최대 O(mn)개의 좌표가 들어갈 수 있으므로 추가 공간 복잡도는 최악의 경우 O(mn)이다.

3. 문제 해결 코드 (Python)

큐에 넣는 순간 O를 T로 바꿔 중복 방문을 막는다. 모든 경계 칸을 시작점으로 처리한 뒤, 마지막에 임시 표시를 원상 복구하면서 내부 영역만 뒤집는다.

from collections import deque


class Solution:
    def solve(self, board: list[list[str]]) -> None:
        rows = len(board)
        cols = len(board[0])
        queue = deque()

        for row in range(rows):
            for col in range(cols):
                is_border = (
                    row == 0
                    or row == rows - 1
                    or col == 0
                    or col == cols - 1
                )
                if is_border and board[row][col] == "O":
                    board[row][col] = "T"
                    queue.append((row, col))

        while queue:
            row, col = queue.popleft()

            for next_row, next_col in (
                (row - 1, col),
                (row + 1, col),
                (row, col - 1),
                (row, col + 1),
            ):
                if not (0 <= next_row < rows and 0 <= next_col < cols):
                    continue
                if board[next_row][next_col] != "O":
                    continue

                board[next_row][next_col] = "T"
                queue.append((next_row, next_col))

        for row in range(rows):
            for col in range(cols):
                if board[row][col] == "O":
                    board[row][col] = "X"
                elif board[row][col] == "T":
                    board[row][col] = "O"

T는 문제 입력에 없는 임시 표시이므로 안전하게 사용할 수 있다. 경계 O를 큐에 넣을 때 바로 T로 바꾸고, 이웃도 큐에 넣기 전에 표시하므로 같은 칸이 큐에 여러 번 들어가지 않는다. solve는 결과를 반환하지 않고 board 자체를 수정한다.

4. 오답 접근과 반례

내부의 모든 O를 바로 X로 바꾸기

가장자리만 O가 아니면 내부 영역이라고 판단하면, 내부 칸이 경계 영역과 연결된 경우를 놓친다.

board = [
    ["X", "X", "X", "X"],
    ["X", "O", "O", "X"],
    ["X", "X", "O", "X"],
    ["X", "O", "X", "X"],
]

위 보드의 가운데 O 영역은 직접 경계에 닿지는 않지만, 아래쪽의 O와 연결되어 있지 않다. 가운데 영역은 뒤집히고 아래쪽 O는 남아야 한다. 반대로 내부 O가 경계의 O와 연결된 경우에는 내부라는 위치만 보고 뒤집으면 안 된다.

경계의 O만 보존하고 연결 영역을 탐색하지 않기

경계 칸 자체만 남기고 그 이웃을 확인하지 않으면 경계에서 한 칸 또는 여러 칸 떨어진 안전한 O를 잘못 뒤집는다.

board = [
    ["X", "O", "X"],
    ["X", "O", "X"],
    ["X", "X", "X"],
]

첫 번째 열이 아니라 위쪽 경계의 O에서 아래쪽 O로 연결되어 있으므로 두 칸 모두 보존해야 한다. 경계에서 BFS를 확장해 연결 관계를 확인해야 한다.

방문 표시를 하지 않고 BFS 큐에 넣기

이웃을 큐에 넣을 때 방문 표시를 하지 않고 큐에서 꺼낼 때만 표시하면 같은 O가 여러 이웃에게서 반복해서 큐에 들어갈 수 있다. 큐에 넣는 순간 T로 바꾸면 각 칸을 한 번만 예약할 수 있다.

복사해 실행할 테스트

아래 검사를 풀이 코드 아래에 붙여 실행하면 내부에 갇힌 O만 뒤집고 경계와 연결된 O는 보존하는지 확인할 수 있다.

board = [list(row) for row in ["XXXX", "XOOX", "XXOX", "XOXX"]]
Solution().solve(board)
assert ["".join(row) for row in board] == ["XXXX", "XXXX", "XXXX", "XOXX"]

5. 공식 예제와 추가 검증

작성한 solve 함수를 Python으로 실행해 공식 예제와 경계 연결 사례를 확인했다. 함수가 보드를 제자리에서 수정하므로 실행 뒤 board의 값을 결과와 비교했다.

공식 예제

입력	기대 결과	확인 결과
`[[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]]`	통과
`[[X]]`	`[[X]]`	통과

추가 검증 1: 경계 O와 연결된 내부 영역

입력: [[X,O,X],[X,O,X],[X,X,X]]
기대 출력: [[X,O,X],[X,O,X],[X,X,X]]
확인 결과: 통과
검증 목적: 경계에서 연결된 내부 O를 보존하는지 확인

추가 검증 2: 내부에 완전히 둘러싸인 한 칸

입력: [[X,X,X],[X,O,X],[X,X,X]]
기대 출력: [[X,X,X],[X,X,X],[X,X,X]]
확인 결과: 통과
검증 목적: 경계와 연결되지 않은 영역을 X로 변경하는지 확인

추가 검증 3: 한 행만 있는 보드

입력: [[O,X,O,O]]
기대 출력: [[O,X,O,O]]
확인 결과: 통과
검증 목적: 모든 칸이 경계인 경우 O를 보존하는지 확인

추가 검증 4: 모든 칸이 O인 보드

입력: [[O,O],[O,O]]
기대 출력: [[O,O],[O,O]]
확인 결과: 통과
검증 목적: 전체 보드가 경계 연결 영역일 때 불필요하게 뒤집지 않는지 확인

6. 다른 풀이 방식 검색 및 비교

Surrounded Regions 공식 문제는 경계와 연결되지 않은 O 영역을 X로 바꾸는 조건을 정의한다.
NeetCode의 Surrounded Regions 설명은 경계 O에서 시작하는 DFS/BFS와 Union-Find 접근을 비교한다.

DFS를 사용해도 경계에서 연결된 영역을 표시한다는 핵심은 같다. 재귀 DFS는 코드가 짧지만 격자가 최대 200 x 200이므로 연결 영역이 매우 깊어질 때 재귀 깊이 문제가 생길 수 있다. 이 글에서는 명시적인 큐를 사용하는 BFS를 선택해 탐색 상태를 안전하게 관리했다.

Union-Find를 사용하면 각 O를 연결 요소로 묶고 경계 전용 노드와 연결되었는지 확인할 수도 있다. 하지만 이 문제에서는 경계에서 실제로 도달 가능한 칸만 표시하면 되므로 BFS가 자료구조와 상태 변화를 직접 설명하기 쉽다.

마무리

Surrounded Regions는 둘러싸인 영역을 직접 찾기보다, 경계와 연결되어 절대 뒤집으면 안 되는 O를 먼저 찾는 문제다. 경계의 O에서 BFS를 시작해 안전한 칸을 T로 표시하고, 탐색 뒤 남은 O만 X로 바꾸면 연결 관계를 정확히 반영할 수 있다. 각 칸을 한 번씩 처리하므로 O(mn) 시간에 입력 보드를 제자리에서 수정할 수 있다.