[백준] P4963

동민·2021년 3월 11일
import java.util.ArrayList;
import java.util.Scanner;

public class P4963 { // 런타임에러 (입력 문제인듯)
	private static int[] dx = { 0, 0, -1, 1, -1, 1, 1, -1 };
	private static int[] dy = { 1, -1, 0, 0, 1, 1, -1, -1 };
	private static int[][] matrix;
	private static boolean[][] visit;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> answer = new ArrayList<>();
		while (true) {
			int w = sc.nextInt();
			int h = sc.nextInt();
			if (w == 0 && h == 0) {
				break;
			}

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

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

			int count = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (!visit[i][j] && matrix[i][j] == 1) {
						count++;
						dfs(i, j);
					}
				}
			}
			answer.add(count);
		}
		for (int ele : answer) {
			System.out.println(ele);
		}
		sc.close();
	}

	private static void dfs(int x, int y) {
		if (visit[y][x])
			return;
		for (int i = 0; i < 8; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			if (isValid(newX, newY) && matrix[newY][newX] == 1) {
				visit[y][x] = true;
				dfs(newX, newY);
			}
		}
	}

	private static boolean isValid(int x, int y) {
		return (x < 0 || x >= matrix[0].length || y < 0 || y >= matrix.length) ? false : true;
	}
}
profile
BE Developer

0개의 댓글