문제 설명
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.
섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
만약 위와 같다면 섬의 개수는 5개입니다.
입력
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
두 번째 줄부터 격자판 정보가 주어진다.
출력
첫 번째 줄에 섬의 개수를 출력한다.
예시 입력 1
1
2
3
4
5
6
7
8
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
1
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;
public class Solution {
int[] dx={0,1,1,1,0,-1,-1,-1}; //x방향 움직임
int[] dy={-1,-1,0,1,1,1,0,-1}; //y방향 움직임
//dfs를 통해 섬의 경계 확인
public void dfs(int x, int y, int[][] board){
if (x< 0|| y< 0|| x>= board.length|| y>= board.length)return;
if(!(board[x][y]==0)){
for (int i = 0; i < dx.length; i++) {
board[x][y]=0; //방문한 지역은 0으로 변경하여 재방문 X
dfs(x+dx[i],y+dy[i],board);
}
}
}
public static void main(String[] args){
Solution s = new Solution();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] board = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = sc.nextInt();
}
}
int answer=0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j]==1) {
answer++; //섬을 찾으면 +1;
s.dfs(i, j, board); //섬의 경계 확인 및 0변환
}
}
}
System.out.println(answer);
}
}