[Leetcode] 130. Surrounded Regions - JS

https://leetcode.com/problems/surrounded-regions/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
문자 'X'와 'O'가 포함된 m x n 매트릭스 보드가 주어지며, 둘러싸인 영역을 'X'로 변경한다

연결: 셀이 인접한 셀과 수평 또는 수직으로 연결됩니다.
지역: 지역을 형성하려면 모든 'O' 셀을 연결하세요.
둘러싸기: 영역을 'X' 셀로 연결할 수 있고 영역 셀이 보드 가장자리에 없는 경우 해당 영역은 'X' 셀로 둘러싸여 있습니다.
매트릭스 보드의 모든 'O' 구역 중 둘러싸인 영역을 'X'로 대체하라.

제한조건
--------------------
- m == board.length
- n = board[i].length
- 1 <= m, n <= 200
- board[i][j]는 'X' 또는 'O'이다.

 

2. 접근 방법 - DFS

접근방법
--------------------
DFS(깊이우선탐색)으로 접근한다.
이 문제의 핵심은 이미 방문했던 구역을 표시하는 방법과 가장 자리 우선 탐색이다.

가장 자리에 닿아있는 'O'들을 먼저 탐색하여 방문했다는 표식으로 '#'으로 값을 바꿔준다.

이후 모든 요소를 순회하면서
'O'인 요소는 'X'로 바꾸고,
'#'인 요소는 'O'로 바꿔준다.

 

 

3. 코드

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    const rows = board.length;
    const cols = board[0].length;

    function dfs(row,col) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || board[row][col] !== 'O') {
            return;
        }
        
        // 방문했던 'O' 구역 표시
        board[row][col] = '#'

        dfs(row - 1, col);
        dfs(row + 1, col);
        dfs(row, col - 1);
        dfs(row, col + 1);
    }

    // 맨위,맨아래 가장자리 탐색
    for (let col = 0; col < cols; col++) {
        dfs(0, col);
        dfs(rows - 1, col);
    }
    
    // 맨왼쪽, 맨오른쪽 가장자리 탐색(맨위와 맨아래는 제외 가능)
    for (let row = 1; row < rows - 1; row++) {
        dfs(row, 0);
        dfs(row, cols - 1);
    }

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            // 가장자리에 닿지 않은 'O' 구역
            if (board[i][j] === 'O') {
                board[i][j] = 'X'
            }
            // 가장자리 탐색으로 방문했던 'O' 구역
            if (board[i][j] === '#') {
                board[i][j] = 'O'
            }
        }
    }
};

 

 

4. 복잡도 분석

- 시간복잡도: O(m * n)

- 공간복잡도: O(1)

 

DFS 탐색으로 접근하는 것 까진 알아냈지만, 가장 자리 우선 탐색하고 방문했던 'O' 구역을 '#'으로 바꾸어 방문 처리하는 방법은 생각하지 못했다.

처음에는 순차적으로 탐색하면서 'O' 구역을 모두 'X'로 바꾸고 가장 자리에 닿아있다면 'O' 구역의 인덱스를 담은 배열을 저장하여 해당 배열을 순회하여 가장 자리에 닿은 'O' 구역들만 'X'로 바꿔주는 방법을 떠올렸다.

하지만 이렇게 접근 시 인덱스를 담은 배열을 추가해야해서 추가 메모리공간도 발생하게 되고, dfs 탐색으로 순차적으로 탐색 시 dfs 탐색 로직 내부에서 'O' 구역이 가장 자리에 닿아있는지 판단하기 위한 로직을 추가해야하므로 하나의 함수 내에서 여러가지 일을 담당하게 되어 복잡한 코드가 된다.

 

그래서 Claude에게 질문하여 내가 접근한 방법에 대해 잘못된 부분을 알아내고 위와 같은 풀이법을 알게되었다.