LeetCode - 130. Surrounded Regions (JavaScript)

Medium, DFS

RunTime : 70 ms / Memory : 53.63 MB

문제

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

• Connect: A cell is connected to adjacent cells horizontally or vertically.
• Region: To form a region connect every 'O' cell.
• Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

A surrounded region is captured by replacing all 'O's with 'X's in the input matrix board.

풀이

• 여기서 주의깊게 생각할 점은, 모든 'O'를 찾는게 아니라 borderLine에 있는 'O'부터 시작해서 탐색해
  그렇게 연결된 것만 제외하고 모두 'X'로 만드는 것이다.

var solve = function(board) {
    if(board.length === 0){
        return null;
    }
    var n = board.length;
    var m = board[0].length;

    var dx = [-1, 1, 0, 0];
    var dy = [0, 0, -1, 1];

    const dfs = (x, y) => {
        board[x][y] = 'W';
        for(let i = 0; i < 4; i++){
            let nx = x + dx[i];
            let ny = y + dy[i];
            if(0<=nx && nx < n && 0<=ny && ny < m && board[nx][ny] === 'O'){
                dfs(nx, ny);
            }
        }
        return
    }

    for(let i = 0; i < n; i++){
        for(let j = 0; j < m; j++){
            if(board[i][j] === 'O' && (i === 0 || i === n-1 || j === 0 || j === m-1)){
                // borderLine에 위치
                dfs(i, j);
            }
        }
    }

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

    return board;
};