[백준] 2667 단지번호 붙이기

DFS를 돌며 4방향 탐색을 하면 풀 수 있다!

num배열에 cnt단지 수를 저장해둔다

마지막에 단지는 cnt개 있으므로 num~ (num+cnt)까지 정렬 후

출력한다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool check[30][30];
int n, arr[30][30],num[1010],cnt;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
 
void dfs(int x,int y) {
    check[x][y] = true;
    num[cnt]++;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (0 <= nx && nx < n && 0 <= ny && ny < n) {
            if (!check[nx][ny] &&arr[nx][ny]) dfs(nx, ny);
        }
    }
}
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf(" %1d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!check[i][j] && arr[i][j]) dfs(i, j), cnt++;
        }
    }
    printf("%d\n", cnt);
    sort(num, num + cnt);
    for (int i = 0; i < cnt; i++) printf("%d\n", num[i]);
}