BOJ 2667 단지번호붙이기

boj 2667 단지번호붙이기

간단한 bfs 구현 문제였다. 단지의 수는 지도를 돌면서 bfs를 도는 횟수를 구해주면 되고, 단지의 면적은 큐에 들어갈 때마다 1씩 증가시키면 된다. 코드에서 num은 단지의 수, area는 단지의 면적, v는 각 단지의 면적을 넣어줄 벡터이다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

string board[27];
bool vis[27][27];
int N;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };
int num;
vector <int> v(num);


int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    queue <pair<int, int>> q;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> board[i];

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (board[i][j] == '0' || vis[i][j] == 1) continue;
            num++;
            q.push({ i,j });
            vis[i][j] = 1;
            int area = 0;

            while (!q.empty())
            {
                area++;
                pair <int, int> cur = q.front();
                q.pop();

                for (int k = 0; k < 4; k++)
                {
                    int nx = cur.first + dx[k];
                    int ny = cur.second + dy[k];
                    if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                    if (board[nx][ny] == '0' || vis[nx][ny] == 1) continue;
                    q.push({ nx,ny });
                    vis[nx][ny] = 1;
                }
            }
            v.push_back(area);
        }
    }
    sort(v.begin(), v.end());
    cout << num << '\n';
    for (int i = 0; i < num; i++)
        cout << v[i]<<'\n';
}