[실1] 2667 - 단지 번호 붙이기

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
 
using namespace std;
 
#define TOTAL_SIZE 5000
#define y first
#define x second
 
pair<int,int> dir[]
{
    { 1, 0 }, // 상
    {-1, 0 }, // 하
    { 0,-1 }, // 좌
    { 0, 1}   // 우
};
 
vector<int> res(TOTAL_SIZE);
int map[TOTAL_SIZE][TOTAL_SIZE]{ 0 };
bool visited[TOTAL_SIZE][TOTAL_SIZE];
int b_size = 0;
int idx = 0;
 
void BFS(int _y, int _x)
{
    // 탐색 시작
    queue<pair<int,int>> q;
    q.push({ _y, _x });
    visited[_y][_x] = true;
    res[idx]++;
 
    while (!q.empty())
    {
        auto front = q.front(); q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            // 다음 좌표
            int ny = front.y + dir[i].y, nx = front.x + dir[i].x;
 
            // 상하좌우 검사
            if (ny < 0       ||
                ny >= b_size ||
                nx < 0       ||
                nx >= b_size)
                continue;
 
            if (!visited[ny][nx] &&
                map[ny][nx] == 1)
            {
                visited[ny][nx] = true;
                q.push({ ny,nx });
                res[idx]++;
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> b_size;
 
    // 문자열 입력
    vector<string> s(b_size);
    for (int i = 0; i < b_size; i++)
        cin >> s[i];
    
    // char형을 int형으로 캐스팅 대입
    for (int y = 0; y < b_size; y++)
    {
        for (int x = 0; x < b_size; x++)
            map[y][x] = s[y][x] - '0';
    }
    // BFS
    for (int y = 0; y < b_size; y++)
    {
        for (int x = 0; x < b_size; x++)
        {
            if (!visited[y][x] &&
                map[y][x] == 1)
            {
                idx++;
                BFS(y, x);
            }
        }
    }
    sort(res.begin(), res.end());
    cout << idx << endl;
    for (auto item : res)
    {
        if (item > 0)
            cout << item << endl;
    }
    return 0;
}