[BOJ] 4963 - 섬의 개수

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/4963

4963번: 섬의 개수

난이도: 실버 2

사용언어: JAVA

 

문제는 간단합니다. 땅은 1, 바다는 0으로 표시된 지도를 하나 주고, 해당 지도에서 섬의 개수를 구하는 문제입니다. 한 땅의 상하좌우 또는 대각선에 또 다른 땅이 존재하면 같은 섬으로 인정됩니다.

 

풀이

이 문제는 dfs를 이용해 어렵지 않게 해결할 수 있습니다. 1을 하나 발견하면 dfs로 이어진 모든 땅을 탐색하며 0으로 만들어주고, 이를 하나의 섬으로 카운트해주기만 하면 됩니다. 너무 전형적인 dfs 문제라 자세한 설명은 생략하도록 하겠습니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
 
    static int [][]d = {{1,0},{1,1},{0,1},{-1,1},{-1, 0},{-1,-1},{0,-1},{1,-1}};
    static int w, h;
    public static void dfs(int x, int y, int[][] arr){
        int i;
        for(i=0;i<8;i++){
            if(x+d[i][0]>=0&&x+d[i][0]<h&&y+d[i][1]>=0&&y+d[i][1] < w){ // 배열의 크기를 벗어나지 않도록 확인
                if(arr[x+d[i][0]][y+d[i][1]] == 1){ // 1이면 (땅이면)
                    arr[x+d[i][0]][y+d[i][1]] = 0; // 0으로 처리해주고
                    dfs(x+d[i][0],y+d[i][1],arr); //또 인접한 땅이 있는지 재귀함수로 확인
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        while(true) {
            String s = br.readLine();
            StringTokenizer st = new StringTokenizer(s);
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            if(w==0 && h==0)
                System.exit(0);
            int[][] arr = new int[h][w];
            int i, j, k;
            for (i = 0; i < h; i++) {
                s = br.readLine();
                st = new StringTokenizer(s);
                for (j = 0; j < w; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
            int cnt=0;
            for(i=0;i<h;i++) {
                for (j = 0; j < w; j++) {
                    if (arr[i][j] == 1) { // 땅을 발견하면
                       dfs(i, j, arr); // dfs를 통해 인접한 땅이 있는지 확인
                        cnt++; // 재귀함수를 탈출하면, 더 이상 인접한 땅이 없다는 뜻이므로 하나의 섬으로 카운트
                    }
                }
            }
            System.out.println(cnt);
        }
    }
}