https://www.acmicpc.net/problem/2583

#include <iostream>
#include <algorithm>
#include <queue>
/*
 *
 *[문제]
 *모눈종이 위에 논금에 맞추어서 K개의 직사각형ㅇ르 그린다.
 *K의 내부를 제외한 부분이 몇 개로 나눠지는 가
 *
 *[입력]
 *M,N K<=100
 *M = 가로
 *N = 세로
 *K 개의 직사각형
 *
 *왼 아래 꼭짓점의 xy, 오른쪽 위 꼭지점의 xy
 *모눈의 왼쪽 아래가 0,0이다.
 *오른쪽 위는 N,M이다.
 *
 *k개의 직사각형들이 모눈 종이 전체를 채우는 경우 없다.
 *
 */

using namespace std;
#define X first
#define Y second

int dx[4]={1,0,-1,0};
int dy[4]= {0,1,0,-1};
int m,n,k;
int board[102][102];
int vis[102][102];


int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    cin >> m >> n>> k;

    while(k--) {
        int x1, y1,x2,y2;
        cin >> x1>>y1 >> x2>> y2;

        for(int j=y1; j<y2; j++) {
            for(int k= x1; k<x2; k++) {
                board[j][k] =1;
            }
        }
    }

    int count =0;
    vector<int> ans;

    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(board[i][j] == 1 || vis[i][j] ==1)continue;

            queue<pair<int,int>>Q;
            vis[i][j] =1;
            Q.push({i,j});
            int width = 1;
            count++;
            while(!Q.empty()) {
                auto 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 || ny <0 || nx >=m || ny >=n)continue;
                    if(board[nx][ny] ==1 || vis[nx][ny] ==1)continue;
                    Q.push({nx,ny});
                    vis[nx][ny] =1;
                    width++;
                }
            }
                ans.push_back(width);
        }
    }
    // for(int i=0; i<m; i++) {
    //     for(int k=0; k<n; k++) {
    //         cout << vis[i][k] << " ";
    //     }
    //     cout << " \n";
    // }
    
    sort(ans.begin(), ans.end());

    cout << count << "\n";
    for(int i: ans) cout << i << " ";

    return 0;

}

이번 문제로 알아낸 BFS의 성질(까먹고 있었던)

• Queue에 Push되는 횟수는 그래프를 탐색한 횟수와 같다
• Queue에서 꺼낸 기준점 +1을 수행하면 시작점 기준 거리를 구할 수 있다.