[アルゴリズム]伯準-4963(島の個数)/Java

21985 ワード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Node {
    int y, x;
    public Node(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Main {
    static int width;//너비
    static int height;//높이
    static int map[][];
    static int visited[][];
                   
    static int dx[] = {1, 0, -1, 0, -1, 1, 1, -1};
    static int dy[] = {0, 1, 0, -1, -1, -1, 1, 1};
    
    
    static Queue<Node> queue;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) {           
            String input = br.readLine();
            // 입력 끝
            if(input.equals("0 0")) {
                return;
            }else {
                StringTokenizer st = new StringTokenizer(input);
                width = Integer.parseInt(st.nextToken());
                height = Integer.parseInt(st.nextToken());
                
                map = new int[height][width];
                visited = new int[height][width];
                
                for(int i=0; i<height; i++) {
                    st = new StringTokenizer(br.readLine());
                    for(int j=0; j<width; j++) {
                        map[i][j] = Integer.parseInt(st.nextToken());
                    }
                }
                
                int count=0;
                queue = new LinkedList<>();
                
                for(int i = 0 ;  i < height ;  i++) {
                    for(int j = 0 ; j < width ; j++) {
                        if(visited[i][j] == 0 && map[i][j]==1) {
                            bfs(i, j);
                            count++;
                        }
                    }
                }
                
                System.out.println(count);
                
            }
        }
    }
    
    public static void bfs(int y, int x) {
        queue.add(new Node(y, x));
        visited[y][x]=1;
        
        while(!queue.isEmpty()) {
            int cury = queue.peek().y;
            int curx = queue.peek().x;
            queue.poll();
            
            for(int i=0; i<8; i++) {
            	int nextX = curx+dx[i];
            	int nextY = cury+dy[i];
                
                
                if(nextX<0 || nextY<0 ||  nextY>=height || nextX>=width) {
                	continue;
                }
                
                if(visited[nextY][nextX] == 1) {
                	continue;
                }
                
                if(map[nextY][nextX]==1) {
                    queue.add(new Node(nextY, nextX));
                    visited[nextY][nextX]=1;
                }
            }
        }
    }
}