[쉽게 배우는 알고리즘 문제풀이]
섬나라 아일랜드
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
만약 위와 같다면 섬의 개수는 5개입니다.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다.
▣ 출력설명
첫 번째 줄에 섬의 개수를 출력한다.
▣ 입력예제 1
7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
▣ 출력예제 1
5
import java.util.Scanner;
public class Island {
private static int answer = 0;
private static int[][] board;
private static int n;
private static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
private static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
board = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = scanner.nextInt();
}
}
solution(board);
System.out.println(answer);
}
private static void solution(int[][] board) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 1) {
answer++;
board[i][j] = 0;
dfs(i, j, board);
}
}
}
}
private static void dfs(int x, int y, int[][] board) {
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && board[nx][ny] == 1) {
board[nx][ny] = 0;
dfs(nx, ny, board);
}
}
}
}