백준 2667번 - 단지번호붙이기

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

유기농 배추 문제와 유사한 문제이다.
집이 연결되어 있는 곳이 전체 몇개 인지를 구하는 문제이다. 

다만, 연결되어 있는 집 각각이 총 몇개의 집이 있는지를 정렬해서 출력해주면 되는 문제이다.



입력을 받을 때 문자열 형태로 들어와서 
cin으로 맵을 표현한 int형 2차원 배열을 계속해서 입력받다보니 올바르지 못한 값이 입력된다.


그렇기 때문에 char형 문자로 입력받고 이 값을 int형 2차원 배열에 넣어줘서 1이 있는 곳을 표시할 수 있도록 하였다. 


그리고 dfs 함수를 구현할 때
cnt 라는 값을 통해서 몇개의 단지 내 집이 있는지를 return해주는 방식으로 구현하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
int N;
int arr[25][25]={0};
int visited[25][25]={0};
 
int dfs(int y,int x){
    
    
    int cnt=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=N || nx<0 || nx>=N)
            continue;
        
        if(arr[ny][nx]==0 || visited[ny][nx])
            continue;
        
        visited[ny][nx]++;
        cnt+=dfs(ny,nx);
    }
    
    return cnt;
}
int main(){
    
    char c;
    cin>>N;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin>>c;
            
            if(c=='1')
                arr[i][j]=1;
        }
    }
 
 
    int ans=0; //총 단지 수
    vector<int> vec; //단지내 집의 수
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(arr[i][j] && !visited[i][j]){
                ans++;
                visited[i][j]++;
                
                vec.push_back(dfs(i,j));
            }
        }
    }
    
    sort(vec.begin(),vec.end());
    
    cout<<ans<<endl;
    for(int i=0;i<vec.size();i++)
        cout<<vec[i]<<endl;
    
    return 0;
}