[BOJ 2667] 단지번호붙이기 C++

난이도: Silver 1
번호: 2667
생성일: March 8, 2023 11:39 AM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

2667번: 단지번호붙이기

C++

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int N;
char map[27][27];
bool visit[27][27];

const int dX[] = {0, 0, -1, 1};
const int dY[] = {-1, 1, 0, 0};

int BFS(int i, int j)
{
    queue<pair<int, int>> Q;
    int cnt = 1;
    Q.push({i, j});
    visit[i][j] = true;

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

        for (int k = 0; k < 4; k++)
        {
            int x = dX[k] + cur.first;
            int y = dY[k] + cur.second;

            if (visit[x][y] || map[x][y] != '1')
                continue;

            Q.push({x, y});
            visit[x][y] = true;
            cnt++;
        }
    }
    return (cnt);
}

int main(void)
{
    vector<int> complex;

    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%s", &map[i][1]);

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (map[i][j] == '1' && !visit[i][j])
                complex.push_back(BFS(i, j));
    sort(complex.begin(), complex.end());

    printf("%lu\n", complex.size());
    for (int i : complex)
        printf("%d\n", i);

    return (0);
}