[BOJ] 백준 4963 섬의 개수

출처: https://www.acmicpc.net/problem/4963

 Input 

5 4

1 1 1 0 1

1 0 1 0 1

1 0 1 0 1

1 0 1 1 1

5 5

1 0 1 0 1

0 0 0 0 0

1 0 1 0 1

0 0 0 0 0

1 0 1 0 1

0 0

 

 Output 

1

9

① 지도 배열을 탐색하며 땅(1) 탐색

② BFS로 땅끼리 연결된 섬을 구분

③ 찾은 섬의 개수 출력.

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
     
    static Queue<Node> queue;
    static int w, h;
    static int[][] arr;
    static int[] rows, cols;
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
             
        // 상하좌우 + 대각선(11시,1시,5시,7시)
        rows = new int[] {-1,1,0,0,-1,-1,1,1};
        cols = new int[] {0,0,-1,1,-1,1,1,-1};
         
         
        while(true) {
            w = Integer.parseInt(sc.next());
            h = Integer.parseInt(sc.next());
             
            // 종료 조건
            if(w == 0 && h == 0) return;
             
            // 입력받은것과 반대로 이차원 배열 할당
            arr = new int[h+1][w+1];
             
            for(int i=1; i<=h; i++) {
                for(int j=1; j<=w; j++) {
                    arr[i][j] = Integer.parseInt(sc.next());
                }
            }
             
            queue = new LinkedList<>();
            int answer = 0;
            for(int i=1; i<=h; i++) {
                for(int j=1; j<=w; j++) {
                    if(arr[i][j] == 1) {
                        // 섬의 개수
                        answer++;
                        //섬이라고 지정되어 있으면 큐에 넣는다.
                        queue.add(new Node(i, j));
                        // 방문표시
                        arr[i][j] = -1;
                        // BFS를 통해 연결된 지점을 알아낸다.
                        BFS();
                    }        
                }
            }
            System.out.println(answer);
                         
        }
    }
    static void BFS() {
        while(!queue.isEmpty()) {
            Node curNode = queue.poll();
            // 걸어갈 수 있는 이동 지점
            for(int i=0; i<8; i++) {
                int next_x = curNode.x + rows[i];
                int next_y = curNode.y + cols[i];
                 
                // 배열을 초과하지 않는 범위내에서
                if(next_x < 1 || next_y < 1) continue;
                if(next_x > h || next_y > w) continue;
                 
                 
                if(arr[next_x][next_y] == 1) {
                    arr[next_x][next_y] = -1; // 방문 표시
                    queue.add(new Node(next_x, next_y));
                }
            }
        }
    }   
}
 
class Node{
    int x,y;
    int connected;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}