[BOJ_4963 | DFS] 섬의 개수

풀이

전형적인 DFS문제로 보여진다.

뭔가 다른 방법이 있진 않을까 해서 DFS를 사용하지 않고 풀려고도 시도해 보았지만

아무래도 DFS로 문제를 해결하는 것이 더 간단해보인다.

DFS란 Depth-First Search 의 약자로

하나의 경로를 우선적으로 끝까지 탐색하는 알고리즘이다.

위 문제를 해결하기 위해서 1로 연결되는 경로를 DFS로 탐색하면서 그 값을 다 2로 바꾸어 준다.

그럼 하나의 점에서 시작된 DFS결과는 상하좌우 대각선으로 연결된 하나의 섬을 전부 2로 바꾼 결과가 되고

아직 2로 바뀌지 않은 지점은 연결되지 않은 섬이므로 카운터의 값을 증가시킨뒤에 다시 DFS를 수행하는 방식이다.

DFS에 익숙하지 않다면 

이 문제를 통해 한번 연습해보는 것이 좋을 듯 하다.

크게 어렵지 않은 난이도로 DFS를 연습해 볼 수 있는 문제였던 것 같다.

소스코드 

import java.util.*;
 
public class BOJ_4963 {
    public static int[][] map;
    public static int cnt;
 
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        while(true){
            int w = input.nextInt(); int h = input.nextInt();
            if(w == 0 && h == 0) break;
            map = new int[h][w];
            for(int i=0;i<h;i++){for(int j=0;j<w;j++)map[i][j] = input.nextInt();}
            //DFS
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(map[i][j] == 1){
                        cnt++; dfs(i, j, h, w);
                    }
                }
            }
            System.out.println(cnt);
            cnt=0;
        }
    }
    public static void dfs(int x, int y, int h, int w){
        if(map[x][y] == 1) map[x][y] = 2;
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if(x+i>=0 && x+i<h && y+j>=0 && y+j<w)
                    if(map[x+i][y+j]==1) dfs(x+i, y+j, h, w);
            }
        }
    }
}