BOJ 4963 - 섬의 개수

문제

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

풀이

기초적인 그래프 탐색 문제이다. 8방향으로 그래프를 탐색해가며 총 컴포넌트(연결되어 있는 노드 집합)의 수를 구해주면 되는데 컴포넌트의 수를 구하기 위해서는 dfs를 몇 번 호출하는지 세어주기만 하면 된다.

방문할 땅과 연결된 모든 땅은 dfs를 통해 방문 표시가 될것이므로 dfs 호출할때 방문하지 않은 땅만 밟으면 총 섬의 개수를 구할 수 있다.

#include<stdio.h>
#include<string.h>
int map[51][51], visit[51][51],w,h;
int dfs(int y,int x){
	int i,j;
	visit[y][x] = 1;
	for(i=-1;i<=1;i++){
		for(j=-1;j<=1;j++){
			if(y+i<1 || x+j<1 || y+i>h || x+j>w) continue;
			if(!visit[y+i][x+j] && map[y+i][x+j])
				dfs(y+i,x+j);
		}
	}
}
int main(){
	while(1){
		int i,j,island=0;
		scanf("%d%d",&w,&h);
		if(!w&&!h) break;
		for(i=1;i<=h;i++){
			memset(map[i],0,sizeof(map[i]));
			memset(visit[i],0,sizeof(visit[i]));
			for(j=1;j<=w;j++)
				scanf("%d",&map[i][j]);
		}
		
		for(i=1;i<=h;i++){
			for(j=1;j<=w;j++){
				if(!visit[i][j] && map[i][j]){
					dfs(i,j);
					island++;
				}
			}
		}
		printf("%d\n",island);
		
	}
}