백준 4963. 섬의 개수 :: 돼지개발자

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

"BFS 탐색, 단지번호 붙이기"

BFS 탐색을 통해 각각 떨어져있는 섬의 개수를 체크하는 것이다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int w,h;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Integer> q = new LinkedList<>();
    static int[] dx = {0,0,1,-1,-1,1,1,-1};
    static int[] dy = {1,-1,0,0,1,1,-1,-1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());
            
            if(w == 0 && h == 0) break;
            
            map = new int[h][w];
            visited = new boolean[h][w];
            
            for (int i = 0; i < h; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            int mark = 0;    // 섬의 개수 
            
            // 전체 맵을 탐색한다.
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    // 바다이거나, 이미 방문한 곳 (다른 섬에 포함된 땅)이라면 탐색하지 않는다.
                    if(map[i][j] != 1 || visited[i][j]) 
                        continue;
                    
                    visited[i][j] = true;
                    q.add(i);
                    q.add(j);
                    mark++;
                    // 특정 지점 i,j 에서 시작해서 갈 수 있는 땅 (상하좌우, 대각선) 
                    // 8방향을 탐색해 갈 수 있을 때 까지 간다.
 
                    while(!q.isEmpty()) {
                        int x = q.poll();
                        int y = q.poll();
                        
                        // 8방향
                        for (int k = 0; k < 8; k++) {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            
                            // 범위를 벗어나거나, 이미 방문했거나 물인 경우는 가지 못한다.
                            if(!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] == 0)
                                continue;
                            
                            visited[nx][ny] = true;
                            q.add(nx);
                            q.add(ny);
                        }
                    }
                }
            }
            System.out.println(mark);
        }
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= h || y < 0 || y >= w) return false;
        return true;
    }
    
}