Leetcode: Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

X로 둘러싸여있는 O들을 X로 치환하는 문제이다.

Solution1. BFS

class Solution:

    def __init__(self):
        self.di = [-1, 1, 0, 0]
        self.dj = [0, 0, -1, 1]


    def solve(self, board: List[List[str]]) -> None:
        if not board: return
        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]

        def setArea(i: int, j: int) -> None:
            queue = [(i, j)]
            l = [(i, j)]

            is_edge = False

            while queue:
                (i, j) = queue.pop(0)

                if i == 0 or i == len(board)-1 or j == 0 or j == len(board[0])-1:
                    is_edge = True

                for x in range(4):
                    new_i = i + self.di[x]
                    new_j = j + self.dj[x]
                    if new_i < 0 or new_i >= len(board) or new_j < 0 or new_j >= len(board[0]) or visited[i][j]:
                        continue
                    elif board[new_i][new_j] == 'O': # Still, we need to check all those adjacent regions
                        queue.append((new_i, new_j))
                        l.append((new_i, new_j))

                visited[i][j] = True

            if not is_edge:
                for (i, j) in l: board[i][j] = 'X'


        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'X' or visited[i][j]: continue
                setArea(i, j)

BFS를 통한 풀이법으로, 'O'인 cell에 대해 setArea()를 실행하면, 이 안에서 해당 cell에 인접한 'O' cell들을 큐에 넣고, surrounded region인지를 확인한다. surrounded region임을 확인하면 (if not is_edge) 해당 영역을 'X'로 업데이트한다. 이미 방문한 영역임을 확인하기 위해 is_visited를 두었다. 

그러나 제출 결과, 하위 5% 라는 충격적인 결과를 보고 재구현을 시도했다. 

Solution2. DFS

class Solution:
    def __init__(self):
        self.di = [-1, 1, 0, 0]
        self.dj = [0, 0, -1, 1]


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

        visited = [[None for _ in range(len(board[0]))] for _ in range(len(board))]

        def is_surrounded(i: int, j: int, l: List[Tuple[int, int]]) -> bool:
            visited[i][j] = True
            l.append((i,j))

            need_to_set = True
            for x in range(4):
                new_i = i + self.di[x]
                new_j = j + self.dj[x]
                if new_i not in range(0, len(board)) or new_j not in range(0, len(board[0])):
                    need_to_set = False
                elif visited[new_i][new_j]:
                    continue
                elif board[new_i][new_j] == 'O':
                    need_to_set = is_surrounded(new_i, new_j, l) and need_to_set
            return need_to_set


        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == 'O' and not visited[i][j]:
                    l = []
                    if is_surrounded(i, j, l):
                        while l:
                            (i, j) = l.pop()
                            board[i][j] = 'X'

이번에는 DFS로 풀어보았다. 비슷하게 is_surrounded에서 인접한 영역들을 찾는 방식이지만, recursive하게 구현되었다. is_surrounded를 수행하며 인접한 'O' cell들을 리스트 안에 담아오며, 리턴값으로 X로 업데이트되어야 하는 영역인지를 recursive하게 알아와서, 최종적으로 True일 경우 l에 있는 cell들을 업데이트한다.

그렇지만 결과는 여전히 하위 10%였다 T T

Solution3. DFS for edge cells only

접근 방식을 조금 달리하였다. board안에서 surrounded region을 찾아 X로 치환하는 것이 아니라, board에서 surrounded region이 아닌 'O' cell들을 찾아서 이것을 제외하고 'X'로 치환하는 방식이다. board에서 'O'가 surrounded region이 아닌 경우는, 결론적으로 해당 'O' 의 영역이 edge cell에 도달되었을 때이다. 예를 들어, 아래와 같은 경우를 살펴보자

X X X X X
X O O O X
X X O X X
X O X X O

이 케이스에서, surrounded region은 가운데 뭉쳐있는 (1,1), (1,2), (1,3), (2,2) 영역임을 쉽게 알 수 있다. 가장자리의 O가 board의 edge영역에 닿아있지 않기 때문이다. 반대로 이야기하면, edge에 닿아있는 'O'가 포함된 영역은 X로 치환되어서는 안된다.

이를 구하기 위해, edge에 있는 'O' cell에 대해서만 DFS를 수행한다. 

class Solution:
    def __init__(self):
        self.di = [-1, 1, 0, 0]
        self.dj = [0, 0, -1, 1]


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

        def check_surrounded(i: int, j: int):
            board[i][j] = 'T'
            for x in range(4):
                new_i = i + self.di[x]
                new_j = j + self.dj[x]
                if new_i in range(0, len(board)) and new_j in range(0, len(board[0])) and board[new_i][new_j] == 'O':
                    check_surrounded(new_i, new_j)

        for j in [0, len(board[0])-1]:
            for i in range(len(board)):
                if board[i][j] == 'O': check_surrounded(i, j)

        for i in [0, len(board)-1]:
            for j in range(len(board[0])):
                if board[i][j] == 'O': check_surrounded(i, j)

        for i in range(len(board)):
            for j in range(len(board[0])):
                board[i][j] = 'O' if board[i][j] == 'T' else 'X'

edge에 닿아있는 'O' 영역에 대해서는 'T'라는 값으로 치환하고, 2와 마찬가지로 recursive하게 해당 cell과 인접해있는 모든 영역을 구한다. edge cell들에 대한 처리가 완료된 이후에, 전체 cell을 순회하면서 'T'로 치환되어있는 cell은 'O'로, 이를 제외하고는 모두 'X' 혹은 surrounded region이므로 'X'로 치환한다. cell의 값 자체를 즉시 치환하기 때문에 앞선 solution들에서처럼 이미 방문한 cell인지를 확인하기 위한 is_visited라는 부가적인 array가 필요하지 않아 메모리 효율성 측면에서도 이득을 볼 수 있었다. 

아직 개선의 여지는 많이 남아있겠지만, 마지막 솔루션을 통해 그나마 만족스러운 결과를 얻을 수 있었다.

 

링크: leetcode.com/problems/surrounded-regions/