14716 현수막

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

DFS나 BFS를 이용하여 연결 요소(Connected Component)의 개수를 세준다.

#include <cstdio>
 
int m,n,map[250][250],ans;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
 
void dfs(int x,int y)
{
    map[x][y]=0;
    for(int i=0;i<8;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=m || ny<0 || ny>=n) continue;
        if(map[nx][ny]==1) dfs(nx,ny);
    }
}
 
int main()
{
    scanf("%d %d",&m,&n);
    for(int i=0;i<m;i++) for(int j=0;j<n;j++) scanf("%d",&map[i][j]);
    for(int i=0;i<m;i++) for(int j=0;j<n;j++)
        if(map[i][j]==1) ans++,dfs(i,j);
    printf("%d\n",ans);
    return 0;
}