(LeetCode) 130. Surrounded Regions

The link : leetcode.com/problems/surrounded-regions/

Surrounded Regions - LeetCode

문제는 다음과 같다. 

1. 4방위가 X로 둘러쌓인 O를 X로 전환한다. 

2. 아래 예시 같은 경우에도 4방위가 X로 둘러쌓인것이 인정된다.

3. 그러므로 테두리에 해당되는 영역은 O,X에 관계없이 전환이 불가능하다.

4. 테두리와 4방위로 이어진 영역 또한 마찬가지다.

---

문제 풀이는 다음과 같다. 

1. 맨 위의 가로 테두리, 맨 아래의 가로 테두리를 for문으로 검사한다.

 검사했을때 'O'라고 표시되어있는 영역은 dfs함수를 통해 '#'으로 바꾸어준다.

2. dfs함수를 통해 해당 영역과 4방위로 이어져있고 + 동시에 'O'값을 지닌 영역은 또다시 dfs를 진행한다. 

3. 세로 테두리도 동일하게 진행한다.

4. 최종적으로 '#'타일인 영역은 'O'로 변환해주고, 'O'타일인 영역은 'X'로 바꾸어준다.

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()<=2||board[0].size()<=2) return;
        int row = board.size(), col = board[0].size();        
        for(int i=0; i<row; i++){ //세로
            if(board[i][0]=='O') dfs(board,i,0);
            if(board[i][col-1]=='O') dfs(board,i,col-1);
        }
        for(int i=0; i<col; i++){ //가로
            if(board[0][i]=='O') dfs(board,0,i);
            if(board[row-1][i]=='O') dfs(board,row-1,i);
        }
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(board[i][j]=='#') board[i][j] = 'O';
                else if(board[i][j]=='O') board[i][j] = 'X';
            }
        }
    }
    void dfs(vector<vector<char>>& board, int i, int j) {
        if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]!='O') return;
        board[i][j] = '#';
        int dy[4] = {1,0,-1,0},dx[4] = {0,1,0,-1};
        for(int a=0; a<4; a++){
            int ny = dy[a]+i;
            int nx = dx[a]+j;
            dfs(board,ny,nx);
        }
    }
};