[Graph General][Medium] 130. Surrounded Regions

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

 

Q. 외부 경계에 접하지 않고, x 에 둘러싸인 영역을 "surrounded"라고 표현할 때, 이 surrounded된 영역의 O를 모두 X로 변환하라. 

 

 

Solution. 

 우선 O로 연결된 영역을 방문관리를 하면서 찾는다. 

 다만, 이때 외부에 걸친 영역이 존재한다면, surrounded되지 않았고, surrounded되었다면 이 영역의 O를 X로 변경한다. 

 

 

코드 

 

void BFS(vector<vector<char>>& board, int ix, int iy, vector<bool>& vVisit)
{
    int H = board.size();
    int W = board[0].size();

    queue<int> qBuff;
    qBuff.push(iy*W + ix);
    vector<int> vRegion;
    bool surrounded = true;
    while(qBuff.size() > 0)
    {
        int idx = qBuff.front();
        qBuff.pop();
        if(vVisit[idx])
            continue;

        vVisit[idx] = true;
        int y = idx / W;
        int x = idx % W;

        if(x==0 || x==W-1 || y==0 || y==H-1)
            surrounded = false;

        vRegion.push_back(idx);

        // up
        if(y>0 && board[y-1][x]=='O')   qBuff.push(idx-W);
        // down
        if(y<H-1 && board[y+1][x]=='O') qBuff.push(idx+W);
        // left
        if(x>0 && board[y][x-1]=='O')   qBuff.push(idx-1);
        // right
        if(x<W-1 && board[y][x+1]=='O') qBuff.push(idx+1);
    }

    if(surrounded)
    {
        for(int q = 0; q < vRegion.size(); ++q)
        {
            int y = vRegion[q]/W;
            int x = vRegion[q]%W;
            board[y][x] = 'X';
        }
    }
}

void solve(vector<vector<char>>& board) 
{
    int H = board.size();
    int W = board[0].size();

    vector<bool> vVisit;
    vVisit.resize(H*W, false);
    for(int y = 0; y < H; ++y)
    {
        for(int x = 0; x < W; ++x)
        {
            int idx = y*W + x;
            if(board[y][x]=='O' && !vVisit[idx])
            {
                BFS(board, x, y, vVisit);
            }
        }
    }
}

 

결과.