파이썬으로 풀어보는 둘러싸인 영역(Surrounded Regions) 문제

문제 소개

2차원 보드에 X와 O가 채워져 있다고 가정해 봅시다. 우리의 목표는 X로 완전히 둘러싸인 모든 영역을 찾아 포획하는 것입니다. 여기서 포획(capture)이란 해당 영역 안에 있는 모든 O를 X로 바꾸는 작업을 의미합니다.

입력 예시

출력 결과

주목할 점은 맨 아래 행 두 번째 칸의 O가 그대로 살아남았다는 것입니다. 이 칸은 보드의 가장자리에 위치하기 때문에 X로 둘러싸일 수 없기 때문입니다.

해결 접근 방법

핵심 아이디어는 매우 직관적입니다. 보드의 가장자리에 있는 O는 절대 포획될 수 없습니다. 따라서 가장자리에서 출발하여 연결된 모든 O를 임시 문자 '1'로 표시해 두면, 나중에 남아 있는 O만 골라서 X로 바꾸면 됩니다. 마지막에는 '1'로 표시했던 칸들을 다시 O로 복원합니다.

전체 알고리즘은 다음 순서로 진행됩니다.

• 보드가 비어 있으면 빈 보드를 그대로 반환합니다.

• 모든 행에 대해 왼쪽 끝 열(board[i][0])과 오른쪽 끝 열(board[i][마지막])에 'O'가 있으면 make_one을 호출합니다.

• 모든 열에 대해 위쪽 끝 행(board[0][i])과 아래쪽 끝 행(board[마지막][i])에 'O'가 있으면 make_one을 호출합니다.

• 전체 보드를 순회하면서 'O'는 'X'로 바꾸고, 임시 표시 '1'은 다시 'O'로 복원합니다.

make_one 함수의 동작 원리

• 좌표(i, j)가 보드 범위를 벗어나거나, 해당 칸이 'X'이거나 이미 방문한 '1'이라면 즉시 종료합니다.

• 현재 칸을 '1'로 표시합니다. 이는 가장자리와 연결되어 안전한 영역임을 의미합니다.

• 상하좌우 네 방향으로 재귀적으로 탐색을 이어갑니다(DFS).

구현 코드

아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.

class Solution(object):
    def solve(self, board):
        if not board:
            return board
        # 좌우 가장자리 확인
        for i in range(len(board)):
            if board[i][0] == 'O':
                self.make_one(board, i, 0)
            if board[i][len(board[0])-1] == 'O':
                self.make_one(board, i, len(board[0])-1)
        # 상하 가장자리 확인
        for i in range(len(board[0])):
            if board[0][i] == 'O':
                self.make_one(board, 0, i)
            if board[len(board)-1][i] == 'O':
                self.make_one(board, len(board)-1, i)
        # 최종 변환: O -> X, 1 -> O
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '1':
                    board[i][j] = 'O'

    def make_one(self, board, i, j):
        if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] == 'X' or board[i][j] == '1':
            return
        board[i][j] = '1'
        self.make_one(board, i+1, j)
        self.make_one(board, i-1, j)
        self.make_one(board, i, j+1)
        self.make_one(board, i, j-1)

복잡도 분석

시간 복잡도는 보드의 모든 칸을 최대 한 번씩만 방문하므로 O(m×n)입니다. 공간 복잡도는 재귀 호출 스택 깊이가 최악의 경우 보드 전체 크기에 비례할 수 있어 O(m×n)입니다.

테스트

입력

[["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"]]