2667번: 단지번호붙이기

DFS로 탐색하면서 단지에 각 집마다 checkNum을 +1한다.

한단지가  종료되면 checkNum을 +1한다.

전체 탐색이 완료된 후 정렬을 통해 오름차순으로 세우고 답을 출력한다.

#include <iostream>
#include <algorithm>
#include <string>
 
typedef struct {
    int y, x;
} dif;
 
dif dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
 
int count[1000] = { 0 };
int check[30][30] = { 0 };
int size;
std::string map[30];
 
void DFS(int checkNum, int y, int x) {
    if (check[y][x]) { return; }
    count[checkNum]++;
    check[y][x] = checkNum;
 
    for (int i = 0; i < 4; i++) {
        int tempY = y + dir[i].y;
        int tempX = x + dir[i].x;
        if (tempY < 0 || tempY >= size || tempX < 0 || tempX >= size) { continue; }
        if (check[tempY][tempX] || map[tempY][tempX] == '0') { continue; }
        DFS(checkNum, tempY, tempX);
    }
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    std::cin >> size;
    for (int i = 0; i < size; i++) {
        std::cin >> map[i];
    }
 
    int checkNum = 1;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (map[i][j] == '0' || check[i][j]) { continue; }
            DFS(checkNum, i, j);
            checkNum++;
        }
    }
    
    std::sort(count, count + 1000);
 
    std::cout << checkNum - 1 << "\n";
    for (int i = 0; i < 1000; i++) {
        if (!count[i]) { continue; }
        std::cout << count[i] << "\n";
    }
 
    return 0;
}