[c++/알고리즘] 백준 2667 단지번호붙이기 : DFS

// 이것역시 시작점이 없으니 dfs를 사용한다고 생각하고 풀어보자
#include <iostream>
#include <queue>
#include <functional> // greater

using namespace std;

int n, hcnt = 1;
int map[26][26];
int ch[26][26];
int dx[4] = { 0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void DFS(int x, int y){
    for(int i=0; i<4; i++){
        if(x+dx[i] < 0 || x+dx[i]>=n || y+dy[i] < 0 || y+dy[i] >= n) continue;

        if(ch[x+dx[i]][y+dy[i]] == 0 && map[x+dx[i]][y+dy[i]] == 1){
            ch[x+dx[i]][y+dy[i]] = 1;
            hcnt++;
            DFS(x+dx[i], y+dy[i]);
        }
    }
}

int main(){
    priority_queue<int, vector<int>, greater<int> > pQ;
    int h, cnt=0;

    cin >> n;
    for(int y = 0; y< n; y++){
        for(int x=0; x<n; x++){
            scanf("%1d", &map[x][y]);
        }
    }

    for(int y = 0; y< n; y++){
        for(int x=0; x<n; x++){
            if(ch[x][y] == 0 && map[x][y] == 1){
                ch[x][y] = 1;
                DFS(x, y);
                cnt++;
                pQ.push(hcnt);
                hcnt = 1;
            }
        }
    }

    cout << cnt << endl;
    while(!pQ.empty()){
        cout << pQ.top() << endl;
        pQ.pop();
    }
    return 0;
}