2667 단지번호 붙이기

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

지도를 스캔하면서 단지(연결요소)를 찾고 BFS나 DFS를 이용하여 각 단지마다 집의 수를 세준다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n,map[25][25],cnt;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
vector<int> ans;
 
void dfs(int x,int y)
{
    cnt++;
    map[x][y]=0;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n || !map[nx][ny])
            continue;
        dfs(nx,ny);
    }
}
 
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        scanf("%1d",&map[i][j]);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++)
        if(map[i][j]==1) cnt=0,dfs(i,j),ans.push_back(cnt);
    sort(ans.begin(),ans.end());
    int size=ans.size();
    printf("%d\n",size);
    for(int i=0;i<size;i++)
        printf("%d\n",ans[i]);
    return 0;
}