백준 2667 단지번호붙이기

// 16분
 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
int map[26][26];
bool check[26][26];
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int dfs(int row, int col) {
    check[row][col] = true;
    int temp = 1;
    for (int k = 0; k < 4; k++) {
        int ny = row + dy[k];
        int nx = col + dx[k];
        if (0 <= nx && nx < n && 0 <= ny && ny < n) {
            if (map[ny][nx] == 1 && !check[ny][nx]) {
                temp += dfs(ny, nx);
            }
        }
    }
    return temp;
}
 
void solve() {
    vector<int> a;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 1 && !check[i][j]) {
                a.push_back(dfs(i, j));
            }
        }
    }
    sort(a.begin(), a.end());
    printf("%d\n", a.size());
    for (int i = 0; i < a.size(); i++) {
        printf("%d\n", a[i]);
    }
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    solve();
    return 0;
}
 

1012 유기농배추와 상당히 유사한 문제. dfs로 접근.

다만,

1012의 경우 집단의 갯수만 출력하면 되었지만

이 문제의 경우 집단을 이루는 구성원의 갯수 또한 출력해야 함.