백준 4963번: 섬의 개수

문제 설명

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

접근법

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

정답

import java.util.*;
import java.io.*;

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

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int M = sc.nextInt();
			int N = sc.nextInt();
			if (N == 0 && M == 0)
				break;

			int[][] 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] == 1) {
						cnt++;
						BFS(new int[] { i, j }, board, N, M);
					}
				}
			}

			System.out.println(cnt);

		}
	}

	public static void BFS(int[] start, int[][] board, int N, int M) {
		board[start[0]][start[1]] = 0;
		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 });
				}
			}
		}
	}

}