[BOJ/2583번영역구하기] c++ / BFS

문제

모눈종이에서 직사각형이 차지하지 않는 영역 개수와, 각 영역의 칸 개수를 출력하는 문제

 

생각

모눈종이의 좌표가 배열이랑 배치가 달라서, 직사각형 영역의 칸에 표시를 어떤식으로 해야할지 생각해봄

N, M 바꾸니까, 시계방향으로 90도 회전하면서 원래의 맵이랑 내용물은 같음

반복문 돌릴 때 M|N 대신 N|M으로 하면 해결!

 

문제풀이

1.직사각형 영역이면 board에 1표시

-주어진 왼쪽 아래 좌표, 오른쪽 위 좌표 이용함( 왼.x~ 오.x-1 & 왼.y ~ 오.y-1 )

2. 직사각형 영역이 아니면 BFS 탐색

-영역의 넓이를 구하기 위해 푸쉬될 때마다 cnt++

-cnt를 벡터 Cnt에 push해줌

3. 벡터를 오름차순 정렬해줌

-sort( 벡터 시작, 벡터 마지막 ) 사용

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define X first
#define Y second
int board[101][101];
int vis[101][101];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int se[4];
int N, M, K;
vector<int> Cnt;
void Input(pair<int, int> a, pair<int, int> b ) {
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) { 
            if ( i >= a.X && i <= b.X && j >= a.Y && j <= b.Y ) {
                board[i][j] = 1;
            }
        }
    }
}
void BFS() {
    for ( int i = 0; i < N; i++ ) {
        for ( int j = 0; j < M; j++ ) {
            if ( board[i][j] == 1 || vis[i][j] ) continue;
            queue<pair<int, int>> Q;
            int cnt = 1;
            Q.push({i, j});
            vis[i][j] = 1;

            while (!Q.empty()) {
                pair<int, int> cur = Q.front(); Q.pop();
                for ( int dir = 0; dir < 4; dir++ ) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];

                    if ( nx < 0 || nx >= N || ny < 0 || ny >= M ) continue;
                    if ( board[nx][ny] || vis[nx][ny] ) continue;

                    vis[nx][ny] = 1;
                    Q.push({nx, ny});
                    cnt++;
                }
            }
            Cnt.push_back(cnt);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> M >> N >> K;
    for ( int i = 0; i < K; i++ ) {
        for ( int j = 0; j < 4; j++ )
            cin >> se[j];

        Input(make_pair(se[0], se[1]), make_pair(se[2]-1, se[3]-1));
    }
    
    BFS();

    int size = Cnt.size();
    sort(Cnt.begin(), Cnt.end());

    cout << size << "\n";
    for ( int i = 0; i < size; i++ ) {
        cout << Cnt[i] << " ";
    }
        
}