[JS] Surrounded Regions

🔒 문제 (LeetCode 130)

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

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

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is 'X' or 'O'.

 

🌊 입출력

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

Example 2:

Input: board = [["X"]]
Output: [["X"]]

 

---

 

🔑 해결

🌌 알고리즘 - DFS

문제를 해석하면 테두리에 존재하는 'O'와 이 좌표로부터 이어진 'O'들만 살아남는다.

따라서 테두리에 있는 'O'에서 시작하여 DFS로 이동 가능한 좌표의 'O'를 '#'로 변환한다.

그 결과에서 '#'는 'X'로, 나머지는 'X'로 변환한다. 

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {
    const [m , n] = [board.length, board[0].length];
    
    const dfs = (r, c) => {
        if(r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== 'O') return;
     
        board[r][c] = '#';
        
        dfs(r-1, c);
        dfs(r+1, c);
        dfs(r, c-1);
        dfs(r, c+1);
    }
    
    // 좌우 테두리 설정
    for(let i = 0; i < m; i++) {
        dfs(i, 0);
        dfs(i, n-1)
    }
    
    // 좌우를 제외한 나머지 테두리 설정
    for(let j = 1; j < n - 1; j++) {
        dfs(0, j);
        dfs(m-1, j);
    }

    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(board[i][j] === 'O') board[i][j] = 'X';
            if(board[i][j] === '#') board[i][j] = 'O';
        }
    }
    
    return board;
};