[백준/Java] 4963 : 섬의 개수(BFS)

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

 

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Baekjoon_4963_섬의개수_BFS {

	static int w, h;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = { 1, -1, 0, 0, -1, -1, 1, 1 };
	static int[] dy = { 0, 0, -1, 1, 1, -1, 1, -1 };

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

		while (true) {
			w = sc.nextInt();
			h = sc.nextInt();
            
			if (w == 0 && h == 0) break;

			map = new int[h][w];
			visit = new boolean[h][w];

			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					map[i][j] = sc.nextInt();
				}
			}

			int cnt = 0;
			Queue<Point> que = new LinkedList<>();

			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (map[i][j] == 1 && !visit[i][j]) {
						cnt++;
						que.add(new Point(i, j));
						visit[i][j] = true;
						while (!que.isEmpty()) {
							Point tmp = que.poll();
							for (int k = 0; k < 8; k++) {
								int nextx = tmp.x + dx[k];
								int nexty = tmp.y + dy[k];
								if (nextx >= 0 && nexty >= 0 && nextx < h && nexty < w && !visit[nextx][nexty] && map[nextx][nexty] == 1) {
									que.add(new Point(nextx, nexty));
									visit[nextx][nexty] = true;
								}
							}
						}
					}
				}
			}
			System.out.println(cnt);
		}
		sc.close();
	}
}

class Point {
	int x;
	int y;

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