13. 섬나라 아일랜드

 

설명

섬 개수 출력

 

 

 

 

예시

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

 

5

 

 

 

 

풀이

섬나라가 몇개 있는지를 찾으면 된다.

 

1. 배열을 문제대로 입력받고

 

2. 입력받은 배열에서 1이 있는곳을 탐색해나간다. 그리고 그 때, answer을 1 증가시키고

DFS(int x, int y) 돌려서 그 해당하는 하나의 섬전체를 0으로 만든다.

 

3. 계속 돌면서 1이 있는곳 = 섬개수를 더해간다....

import java.util.*;


class Main {

	static int[] dx= {0,1,1,1,0,-1,-1,-1};
	static int[] dy = {-1,-1,0,1,1,1,0,-1};
	static int n;
	static int [][] board;
	static int cnt=0;
	
	
	public void DFS(int x, int y) {
		
		board[x][y]=0;
		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);
			}
		}
		
		
	}
	
	public void solution(int[][] board) {
		
		for(int i=0; i<n ;i++) {
			for(int j=0; j<n; j++) {
				if(board[i][j]==1) {
					cnt++;
					DFS(i,j);
				}
			}
		}
	}
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		
		n= sc.nextInt();
		
		board= new int[n][n];
		
		for(int i=0; i<n ;i++) {
			for(int j=0; j<n; j++) {
				board[i][j]=sc.nextInt();
			}
		}
		
		T.solution(board);
		
		System.out.println(cnt);

	}

	
}