[BaekJoon] 2667 단지번호붙이기 :: monton

문제

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

풀이

dfs를 이용하여 단지를 라벨링 한 후,

갯수를 세어 sort하여 출력

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N,num;
int arr[26][26];
int visit[26][26];
int sortnum[700];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
void func(int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= N) return;
    if (visit[x][y] || !arr[x][y]) return;
 
    visit[x][y] = 1;
    arr[x][y] = num;
    for (int i = 0; i < 4; i++) {
        func(x + dir[i][0], y + dir[i][1]);
    }
}
 
int main() {
    cin >> 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 (!visit[i][j] && arr[i][j]) num++, func(i, j);
        }
    }
    int a = 1;
    for (int z = 0; z < num; z++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == a) sortnum[z]++;
            }
        }
        a++;
    }
 
    sort(sortnum, sortnum + num);
    cout << num <<endl;
    for (int i = 0; i < num; i++) {
        cout << sortnum[i] <<endl;
    }
}