[LeetCode] 130. Surrounded Regions

😎풀이

해당 문제는 상, 하, 좌, 우가 X로 둘러쌓인 O가 X로 변환된다는 전제로 어떤 변화가 일어나야 하는지 묻는 문제이다.

풀이 절차는 다음 3가지 이다.

1. 모서리의 O는 X가 될 수 없다. (모서리 이므로 4 방면이 모두 둘러쌓일 수 없음)
2. 모서리의 O와 연결된 O는 X가 될 수 없다. (1.의 셀이 둘러쌓일 수 없는 이유로)
3. 모서리와 연결되지 않은 O는 모두 X가 된다. (모서리와 연결되지 않았다는 것은 X로 둘러쌓였음을 의미

/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
    const rowLen = board.length
    const colLen = board[0].length
    // 가장자리 요소와 연결된 모든 요소들을 T로 변환
    // 열 확인
    for(let i = 0; i < rowLen; i++) {
        // 첫 열
        dfs(i, 0)
        // 마지막 열
        dfs(i, colLen - 1)
    }
    // 행 확인
    for(let i = 0; i < colLen; i++) {
        // 첫 행
        dfs(0, i)
        // 마지막 행
        dfs(rowLen - 1, i)
    }
    // 모서리에 연결되지 않은 'O'는 모두 캡쳐 대상
    for(let i = 0; i < rowLen; i++) {
        for(let j = 0; j < colLen; j++) {
            if(board[i][j] === 'T') {
                board[i][j] = 'O'
                continue
            }
            board[i][j] = 'X'
        }
    }
    function dfs(row: number, col: number) {
        if(row < 0 || row >= rowLen || col < 0 || col >= colLen || board[row][col] !== 'O') return

        board[row][col] = 'T'

        // 상 하 좌 우 탐색
        dfs(row - 1, col)
        dfs(row + 1, col)
        dfs(row, col - 1)
        dfs(row, col + 1)
    }
};