파이썬(Python)으로 푸는 둘러싸인 영역(Surrounded Regions) 문제

문제 정의

2차원 보드(board)에 두 종류의 문자 X와 O가 있다고 가정해 보겠습니다. 이때 X로 완전히 둘러싸인(surrounded) 모든 영역을 찾아 포획(capture)하는 것이 목표입니다. 여기서 포획이란 해당 영역 내부의 모든 'O'를 'X'로 바꾸는 작업을 의미합니다.

단, 한 가지 중요한 규칙이 있습니다. 보드의 테두리(가장자리)와 맞닿아 있는 'O'는 사방이 X로 둘러싸여 있지 않기 때문에 포획 대상에서 제외되며, 그대로 'O'로 남아 있어야 합니다.

예시 입력

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

결과를 자세히 보면, 보드 중앙의 'O'들은 X로 둘러싸여 있어 모두 'X'로 변경되었습니다. 반면 마지막 행의 'O'는 보드 가장자리와 인접해 있어 포획 대상이 아니므로 그대로 유지된 것을 확인할 수 있습니다.

풀이 전략

이 문제는 역발상으로 접근하면 깔끔하게 해결할 수 있습니다. 포획되어야 할 영역을 일일이 찾는 대신, 포획될 수 없는 영역, 즉 테두리와 연결된 'O'들을 먼저 임시 문자 '1'로 표시해 두는 방식입니다. 전체 과정은 다음과 같습니다.

보드가 비어 있다면 그대로 빈 보드를 반환합니다.
왼쪽·오른쪽 열(첫 번째 열과 마지막 열)을 순회하면서 값이 'O'인 칸이 있으면 make_one() 함수를 호출해 연결된 모든 'O'를 '1'로 표시합니다.
같은 방식으로 위쪽·아래쪽 행(첫 번째 행과 마지막 행)에 대해서도 동일한 작업을 수행합니다.
모든 테두리 검사가 끝나면 보드 전체를 다시 순회합니다. 이때 아직 'O'로 남아 있는 칸은 둘러싸인 영역이므로 'X'로 바꾸고, 임시 표시였던 '1'은 원래대로 'O'로 되돌립니다.

make_one 함수(DFS)의 동작 원리

현재 좌표 (i, j)가 보드 범위를 벗어나거나, 해당 칸이 이미 'X' 또는 '1'이라면 재귀 호출을 종료(return)합니다.
그렇지 않다면 현재 칸을 '1'로 표시합니다.
상·하·좌우 네 방향, 즉 (i+1, j), (i-1, j), (i, j+1), (i, j-1) 좌표에 대해 재귀적으로 make_one을 호출하여 연결된 모든 'O'를 표시합니다.

구현 예제

다음 파이썬 코드를 통해 전체 로직을 확인해 보세요.

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)
        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'
        return board
    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)
ob1 = Solution()
print(ob1.solve([["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]))

입력

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

복잡도 분석

보드의 크기를 m×n이라 할 때, 각 칸은 상수 번만 방문되므로 시간 복잡도는 O(m×n)입니다. 다만 재귀 호출 스택이 최악의 경우 보드 전체 크기만큼 깊어질 수 있어 공간 복잡도 역시 최대 O(m×n)입니다. 만약 매우 큰 보드에서 재귀 깊이 제한(RecursionError)이 걱정된다면, 명시적인 스택이나 큐를 사용하는 반복적 DFS/BFS 방식으로 make_one 함수를 대체하면 됩니다.

파이썬(Python)으로 푸는 둘러싸인 영역(Surrounded Regions) 문제 – DFS 활용 풀이