[JAVA/코딩테스트] 섬나라 아일랜드

설명

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.

각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.

섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

만약 위와 같다면 섬의 개수는 5개입니다.

입력

첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.

두 번째 줄부터 격자판 정보가 주어진다.

출력

첫 번째 줄에 섬의 개수를 출력한다.

예시 입력 1 

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

예시 출력 1

5

 

 

 

import java.util.*;

class Point{

    int x, y;

    public Point(int tmpX, int tmpY) {
        this.x = tmpX;
        this.y = tmpY;
    }

}

public class Main {

    static int n;
    static int[] disX = {0, 1, 0, -1, -1, 1, -1, 1};
    static int[] disY = {1, 0, -1, 0, -1, -1, 1, 1};
    static int[][] array;
    static int[][] dis;
    static Queue<Point> qu = new LinkedList<>();
    static int answer = 0;

    public void DFS(int x, int y){

        if(dis[x][y] == 1){
            return;
        }else{

            dis[x][y] = 1;

            for (int i = 0; i < 8; i++) {

                int tmpX = x + disX[i];
                int tmpY = y + disY[i];

                if(tmpX >= 0 && tmpY >= 0 && tmpX < n && tmpY < n && array[tmpX][tmpY] == 1){
                    DFS(tmpX, tmpY);
                }

            }

        }


    }

    public static void main(String[] args) {

        Main main = new Main();

        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        array = new int[n][n];
        dis = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                array[i][j] = in.nextInt();
                if(array[i][j] == 1){
                    qu.offer(new Point(i, j));
                }
            }
        }


        while(!qu.isEmpty()){
            Point tmp = qu.poll();
            if(dis[tmp.x][tmp.y] != 1){
                main.DFS(tmp.x,tmp.y);
                answer++;
            }
        }

        System.out.println(answer);

    }
}