Leetcode - 130. Surrounded Regions

문제

상하좌우가 X로 둘러쌓인 O영역만 X로 flip해라.
(아래 예제에서 맨 아래 행에있는 O는 경계에 걸쳐있기 때문에 X로 flip할 수 없음)

https://leetcode.com/problems/surrounded-regions/

해결 아이디어

• 처음에 한번의 DFS 재귀함수에서 모든 경우를 flip 해보려고 했는데, 경계 'O' 경우를 함께 해결하기가 너무 어려웠음. -> 실패

• 그리고 솔루션에서 힌트(경계만 미리 marking)를 받음.

  1. 사전에 경계'O' 경우는 dfs로 'E' 로 모두 바꿔놓고.
  2. 그리고 그 뒤 O를 모두 X로 바꿈.
  3. 마지막으로 다시 배열을 순회하면서 E를 O로 바꿈.

  시간복잡도 O(mn) 공간복잡도 O(1)

해결

경계의 O경우만 DFS재귀 순회하고, 그 뒤부터는 재귀호출 필요없이 배열을 리니어하게 탐색하면 됨.

class Solution {
    int rsize;
    int csize;

    void flip_by(vector<vector<char>>& board, int r, int c) {
        if (r < 0 || r >= rsize || c < 0 || c >= csize)
            return;
        if (board[r][c] == 'E' || board[r][c] == 'X') {
            return;
        }
        board[r][c] = 'E';
        flip_by(board, r + 1, c);
        flip_by(board, r - 1, c);
        flip_by(board, r, c + 1);
        flip_by(board, r, c - 1);
    }
public:
    void solve(vector<vector<char>>& board) {
        rsize = board.size();
        csize = board[0].size();
        
        /* mark boader's 'O' to 'E' */
        /* check col 0 and last boarer */
        for (int i = 0; i < rsize; i++) {
            if (board[i][0] == 'O')
                flip_by(board, i, 0);
            if (board[i][csize - 1] == 'O')
                flip_by(board, i, csize - 1);
        }
        /* check row 0 and last boarer */
        for (int i = 0; i < csize; i++) {
            if (board[0][i] == 'O')
                flip_by(board, 0, i);
            if (board[rsize - 1][i] == 'O')
                flip_by(board, rsize - 1, i);
        }
        /* convert O to X */
        for (int i = 1; i < rsize - 1; i++) {
            for (int j = 1; j < csize - 1; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
        /* convert E to O */
        for (int i = 0; i < rsize; i++) {
            for (int j = 0; j < csize; j++) {
                if (board[i][j] == 'E')
                    board[i][j] = 'O';
            }
        }
    }
};