[c++][BOJ][2667] 단지번호 붙이기

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

2667번: 단지번호붙이기

단지의 수와 단지마다 있는 아파트의 개수를 구하는 문제입니다.

 

가장 먼저 배열을 세팅하고 , 한칸씩 돌아가면서 아파트가 있는 곳을 찾습니다.

 

아파트가 있다면 , 함수에서 인접해있는 아파트(단지) 를 구합니다. 아파트의 수는 단지 내 아파트의 수가 되고 , 그 수를 모두 구한 후 다음칸을 확인하기 전에 벡터 안에 저장합니다.

 

모두 구한 후 , bcount의 개수는 단지의 개수를  , countAll 벡터는 단지 내 아파트의 순서를 무작위로 저장하고 있습니다.

 

countAll을 마지막에 sort해준 후 , 출력합니다(최대 25 X 25 칸이라 sort에 큰 부담 없음)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int arr[25][25] = {0};
vector<int> countAll;
int allCount = 0;
int bcount = 0;

void find(int x, int y, int xMax,int yMax, int before){
    if(x == xMax || y == yMax || x < 0 || y < 0){
        return;
    }
    
    allCount++;
    arr[x][y] = 0;

    if(before == 0){
        bcount++;
    }
    if(arr[x+1][y] == 1){
        find(x+1 , y, xMax, yMax, 1);
    }
    if(arr[x][y+1] == 1){
        find(x , y+1, xMax, yMax, 1);
    }
    if(arr[x-1][y] == 1){
        find(x-1 , y, xMax, yMax, 1);
    }

    if(arr[x][y-1] == 1){
        find(x , y-1, xMax, yMax, 1);
    }
 
}

int main(){
    int n;
    cin >> n;

    for(int i=0; i<n; i++){
        string str;
        cin >> str;
        
        for(int j=0; j<n; j++){
            char c = str[j];
            arr[i][j] = c - '0';
        }
    }
    for(int q=0; q<n; q++){
        for(int w=0; w<n; w++){
            if(arr[q][w] == 1){
                allCount = 0;
                find(q, w, n, n, 0);
                countAll.push_back(allCount);
            }
        }
    }
    cout << bcount << '\n';
    sort(countAll.begin(), countAll.end());
    
    for(int k=0; k<countAll.size(); k++){
        cout << countAll[k] << '\n';
    }
}