백준 14716번: 현수막

문제 설명

• https://www.acmicpc.net/problem/14716

접근법

• 8방으로 BFS탐색을 진행합니다.

정답

import java.util.*;

public class Main {
	static int[] dx = { 1, 0, -1, 0, 1, 1, -1, -1 };
	static int[] dy = { 0, 1, 0, -1, 1, -1, 1, -1 };
	static int N, M;
	static int[][] board;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		board = new int[N][M];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}

		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] != 0) {
					cnt++;
					board[i][j] = 1;
					BFS(new int[] { i, j });
				}
			}
		}
		System.out.println(cnt);
	}

	public static void BFS(int[] start) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		while (!q.isEmpty()) {
			int[] now = q.poll();
			for (int d = 0; d < 8; d++) {
				int nx = now[0] + dx[d];
				int ny = now[1] + dy[d];
				if (0 <= nx && nx < N && 0 <= ny && ny < M && board[nx][ny] == 1) {
					board[nx][ny] = 0;
					q.add(new int[] { nx, ny });
				}
			}
		}

	}

}