(C++) - 백준(BOJ) 2583번 : 영역 구하기

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
queue <pair <int,int> > q;
vector <int> dcnt(101);
int la,ra,lb,rb, m, n, k, a[101][101],c[101][101], dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 },cnt;

void BFS(int i,int j,int cnt)
{
    q.push(make_pair(i,j));
    dcnt[cnt]++;
    c[i][j] = 1;
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)//4방향을 살펴본다
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(1<=nx && nx <=m && 1<=ny && ny <=n)//nx,ny가 행렬의 범위 안에 있다면
                if (c[nx][ny] == 0 && a[nx][ny] == 1)
                {
                    c[nx][ny] = 1;
                    q.push(make_pair(nx, ny));
                    dcnt[cnt]++;
                }
        }
    }
}
int main() {
    cin >> m >> n >> k;//m행,n열,직사각형 개수
    for (int i = 1; i <= 100; i++)//모든 a의 칸을 1로 초기화
        for (int j = 1; j <= 100; j++)
            a[i][j] = 1;
    for (int i = 0; i < k; i++)//a의 영역을 만들어준다 - > 직사각형 범위의 칸은 0으로 만들어줌
    {
        cin >> la >> lb >> ra >> rb;
        for (int i = m - rb + 1; i <= m - lb; i++)
            for (int j = la + 1; j <= ra; j++)
                a[i][j] = 0;
    }
    for (int i = 1; i <= m; i++)//모든 점에 대해 같은 영역인지 판단하는 BFS탐색을 시행한다.
        for (int j = 1; j <= n; j++)
            if (a[i][j] == 1 && c[i][j] == 0)
                BFS(i, j, ++cnt); 
    sort(dcnt.begin(),dcnt.end());//영역의 넓이를 오름차순으로 정렬
    cout << cnt << '\n';
    for (int i = 1; i <= 101; i++)
        if(dcnt[i]!=0)
            cout << dcnt[i] << ' ';
}