[PS] 인프런 강의 - BFS 3. 섬나라 아일랜드

문제

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

풀이

DFS로 푼 풀이와 거의 같다. 그냥 BFS로 바뀌었을 뿐이다.

개인적으로 BFS로 푸는 게 문제에 더 어울리는 풀이인 것 같다.

 

코드

import java.awt.Point;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[][] map;
    static int answer; 

    public static void BFS(int x, int y) {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x,y));

        while(!Q.isEmpty()) {
            Point pos = Q.poll();

            for(int i=0; i<8; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];

                if(nx>=0 && nx<n && ny>=0 && ny<n && map[nx][ny] == 1) {
                    map[nx][ny] = 0;
                    Q.add(new Point(nx, ny));
                }
            }
        }

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        map = new int[n][n];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                map[i][j] = in.nextInt();
            }
        }

        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(map[i][j] == 1) {
                    answer++;
                    map[i][j] = 0; //출발
                    BFS(i, j);
                }
            }
        }   
        System.out.println(answer);

    }
}