[백준/DFS/C++] 2667번 단지번호 붙이기

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

2667번: 단지번호붙이기

dfs를 활용하여 풀었다

#include <bits/stdc++.h>

using namespace std;

int n;
int graph[26][26];
vector<int> num;
int sum = 0;

bool dfs(int x, int y){
    // 범위 밖인 경우
    if(x<=-1 || x>=n || y<=-1 || y>=n){ 
        return false;
    }
    if(graph[x][y] == 1){ // 집인 경우
        sum += 1; // 집 수 +1
        graph[x][y] = 0; // 방문했다는 표시로 0으로 바꿈
        // 상하좌우 방문
        dfs(x-1, y);
        dfs(x+1, y);
        dfs(x, y-1);
        dfs(x, y+1);
        return true;
    }
    return false;
}

int main(void) {
    cin >> n;

    for(int i=0; i<n; i++){ // 그래프 입력받기
        for(int j=0; j<n; j++){
            scanf("%1d", &graph[i][j]);
        }
    }
    int result = 0; // 단지 수
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(dfs(i,j)){ // 현재 위치에서 dfs 수행
                num.push_back(sum); // 집의 수 벡터에 넣음
                result++; // 단지수 +1
                sum = 0; // 집의 수 초기화
            }
        }
    }
    cout << result << endl; // 단지수
    // 집의 수 오름차순으로 정렬
    sort(num.begin(), num.end());
    for(int i : num){
        cout << i << endl;
    }

    return 0;
}