[실1] 2583 - 영역 구하기 bfs

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

using namespace std;
using int_pair = pair<int, int>;

#define SIZE 1000
#define x first
#define y second

// 상 하 좌 우
int_pair arr_pos[]
{
    {0, 1},
    {0,-1},
    {-1,0},
    {1, 0}
};

queue<int_pair> q;
bool graph[SIZE][SIZE]{ false };

int zone = 0;
// w:넓이, h:높이, k:테스트 개수
int w, h, k;

int BFS()
{
    int block_cnt = 0;

    while (!q.empty())
    {
        auto front = q.front(); q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = front.x + arr_pos[i].x;
            int ny = front.y + arr_pos[i].y;

            if (nx < 0 ||
                ny < 0 ||
                nx >= w ||
                ny >= h)
                continue;

            if (!graph[nx][ny])
            {
                graph[nx][ny] = true;
                q.push({ nx,ny });
                block_cnt++;
            }
        }
    }
    zone++;
    return block_cnt;
}

int main()
{
    cin >> w >> h >> k;
    vector<pair<int_pair, int_pair>> tmp_vec;
    vector<int> result;
    tmp_vec.resize(k);

    for (int i = 0; i < k; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 좌표 저장
        //tmp_vec.push_back({ {x1, y1}, {x2, y2} });

        for (int i = y1; i < y2; i++)
            for (int j = x1; j < x2; j++)
                graph[i][j] = true;
    }
    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
            if(!graph[i][j])
            {
                q.push({ i,j });
                auto val = BFS();
                result.push_back((val == 0) ? 1 : val);
            }
        }
    }
    sort(result.begin(), result.end());
    // 정답 출력
    cout << zone << endl;

    for (auto item : result)
        cout << item << ' ';
}