[백준] 2667. 단지번호붙이기(c++)

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

전형적인 완탐 bfs 문제였다.

 

---

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <limits.h>
#include <queue>
#include <set>
#include <math.h>
#include <stack>
#include <deque>

using namespace std;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, cnt =0;

    cin >> n;

    vector<string> arr(n);
    vector<vector<bool>> visited(n, vector<bool>(n));
    queue<pair<int, int>> q;
    vector<int> ans;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j] && arr[i][j] != '0') {
                q.push({ i,j });
                visited[i][j] = true;
                cnt++;
                ans.push_back(1);
                while (!q.empty()) {
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();

                    for (int k = 0; k < 4; k++) {
                        int ny = y + dy[k];
                        int nx = x + dx[k];

                        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                        if (visited[ny][nx] || arr[ny][nx] == '0') continue;
                        q.push({ ny,nx });
                        visited[ny][nx] = true;
                        ans[cnt - 1]++;
                    }
                }
            }
        }
    }

    cout << cnt << '\n';

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

    for (int i = 0; i < cnt; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}