백준 4963번 문제. 섬의 개수

백준 4963번 문제. 섬의 개수

[Point] DFS를 이용해 그래프의 연결요소(Connected Component)의 갯수를 찾아내라

그래프의 연결요소란 이동가능한 "뭉치"라고 생각하면 된다. 이 문제에서 요구하는 섬의 정의와 그 갯수는 그래프의 연결요소 개수와 일맥상통한다.

우선 w=0,h=0이 들어오지 않는 이상 무한루프로 케이스를 입력받고 결과값을 출력하면 된다.

매 과정이 반복될때마다 방문여부를 알려주는 visit[][]과 섬의 갯수를 알려주는 cnt 변수를 도로 초기화하는 것을 잊으면 안된다.

코드는 간단하다.

방향배열 dx,dy를 이용해 탐색가능한 8개의 주변 정사각형을 검사한다.

①이동가능하면서(map[][]=1) ②맵을 벗어나지 않는 유효한 범위(nx와 ny의 범위 체크), ③마지막으로 한번도 방문한 적이 없는 곳(visit=0)이라면,

함수를 재귀호출하여 visit 값을 1로 변경해주면 된다. 더이상 주변에 탐색가능한 섬이 없을때 DFS함수는 종료되고 cnt값이 1 증가하게 된다. 

#include <stdio.h>
 
int visit[50][50]={0};
int map[50][50];
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int w,h;
 
void DFS(int x,int y){
    int i,nx,ny;
    visit[x][y]=1;
 
    for(i=0;i<8;i++){
        nx=x+dx[i];
        ny=y+dy[i];
 
        if(nx>=h || nx<0 || ny>=w || ny<0){
            continue;
        }
 
        if(visit[nx][ny]==0 && map[nx][ny]==1){
            DFS(nx,ny);
        }
    }
 
}
    
 
 
int main(){
 
    int cnt;
    int i,j;
 
    while(1){
        scanf("%d%d",&w,&h);
        if(w==0 && h==0){
            return 0;
        }
 
        for(i=0;i<50;i++){
            for(j=0;j<50;j++){
                visit[i][j]=0;
            }
        }
        cnt=0;
 
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                scanf("%d",&map[i][j]);
            }
        }
        
 
        for(i=0;i<h;i++){
            for(j=0;j<w;j++){
                if(visit[i][j]==0 && map[i][j]==1){
                    DFS(i,j);
                    cnt++;
                }
            }
        }
        printf("%d\n",cnt);
 
    }
 
    return 0;
}