2667번: 단지번호붙이기(15분)

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

구현 15분

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
int Maps[25][25], N, Sum; 
vector<int> VecAnswer;

int Dr[4] = { -1, 0, 1, 0 };
int Dc[4] = { 0, 1, 0, -1 };

void BFS(int StartRow, int StartCol)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(StartRow, StartCol));

    Maps[StartRow][StartCol] = 0;

    while (!Q.empty())
    {
        int CurrentRow = Q.front().first;
        int CurrentCol = Q.front().second;

        Q.pop();

        for (int k = 0; k < 4; ++k)
        {
            int NextRow = CurrentRow + Dr[k];
            int NextCol = CurrentCol + Dc[k];

            if (NextRow < 0 || NextCol < 0 || NextRow >= N || NextCol >= N ||
                Maps[NextRow][NextCol] == 0) continue;

            Maps[NextRow][NextCol] = 0;
            Q.push(make_pair(NextRow, NextCol));
            ++Sum;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("input.txt", "rt", stdin);

    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        string StrData;
        cin >> StrData;
        for (int j = 0; j < N; ++j)
        {
            Maps[i][j] = StrData[j] - '0';
        }
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (Maps[i][j] == 1)
            {
                Sum = 1;
                BFS(i, j);
                VecAnswer.push_back(Sum);
            }
        }
    }

    sort(VecAnswer.begin(), VecAnswer.end());

    cout << VecAnswer.size() << '\n';

    for (auto it : VecAnswer)
    {
        cout << it << '\n';
    }

    return 0;
}