[LeetCode] 130. Surrounded Regions

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

Surrounded Regions - LeetCode

Surrounded Regions - Medium

 

X로 둘러싸인 O를 모두 X로 바꾸는 문제.

배열의 끝부분에 있는 O는 둘러싸여있지 않다고 판단을 하는 문제다.

바꿔 생각하면 끝부분에 있는 O와 연결된 O는 모두 안바뀌고, 나머지 O는 X로 바꿔주면 된다.

 

전체 풀이 코드

class Solution {
public:
    vector<vector<char>> b;
    void solve(vector<vector<char>>& board) {
        this->b = board;
        for (int i=0; i<board.size(); i++) for (int j=0; j<board[0].size(); j++) if (i==0 || j==0 || i==board.size()-1 || j==board[0].size()-1) run(i,j);
        for (int i=0; i<board.size(); i++) for (int j=0; j<board[0].size(); j++) board[i][j] = this->b[i][j]=='#'?'O':'X';
    }
    void run(int i, int j) {
        if (this->b[i][j]=='O') {
            this->b[i][j] = '#';
            if (i) run(i-1,j);
            if (j) run(i,j-1);
            if (i<this->b.size()-1) run(i+1, j);
            if (j<this->b[0].size()-1) run(i,j+1);
        }
    }
};