[leetcode] 130. Surrounded Regions

class Solution {
public:
    vector<vector<int>> visited;
    vector<vector<char>> answer;
    
    int mvX[4] = {0,0,1,-1};
    int mvY[4] = {1,-1,0,0};
    
    void DFS(int i, int j, vector<vector<char>>& board){
        if(visited[i][j]) return;
        
        visited[i][j] = 1;
        answer[i][j] = 'O';
        
        for(int k = 0; k<4; k++){
            int newI = i + mvX[k];
            int newJ = j + mvY[k];
            
            if(newI < 0 || newI >= visited.size() || newJ < 0 || newJ >= visited[0].size()) continue;
            if(board[newI][newJ] == 'O') DFS(newI, newJ, board);
        }
    }
    
    void solve(vector<vector<char>>& board) {
        visited.assign(board.size(), vector<int>(board[0].size(), 0));
        answer.assign(board.size(), vector<char>(board[0].size(), 'X'));
        
        for(int i = 0; i<board[0].size(); i++){
            if(board[0][i] == 'O') DFS(0, i, board);
            if(board[board.size() - 1][i] == 'O') DFS(board.size() - 1, i, board);
        }
        
        for(int i = 1; i<board.size() - 1; i++){
            if(board[i][0] == 'O') DFS(i, 0, board);
            if(board[i][board[0].size() - 1] == 'O') DFS(i, board[0].size() - 1, board);
        }
        
        board = answer;
    }
};

 

DFS/BFS 문제가 풀고싶어서 골라보았습니다.

굉장히 간단한문제로 단순하게 외각부분만 DFS를 돌리고 그 결과를 리턴해주면 됩니다.

다른 풀이를 보아도 대부분 큰차이가 안나서 요정도로 정리하면 될 것 같습니다.

 

시간복잡도 : O(NlogN)