[Algorithm]알고리즘 자바_66 섬나라 아일랜드

💬 문제 설명

N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.

섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

만약 아래와 같다면 섬의 개수는 5개입니다.

 

🔨 입출력 예

- 입력 

• 첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
• 두 번째 줄부터 격자판 정보가 주어진다.

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

 

 

💻 Solution.java

import java.util.*;

public class Main {
	static int answer = 0, n;
    
    // 앞 뒤 양옆, 대각선의 좌표 정보
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	
    // x, y 좌표를 중심으로 DFS 시작
	public 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];
			
            // 경계선 검사 & 땅(1)인 값 찾기
			if(nx >= 0 && ny >= 0 && nx < n && ny < n && board[nx][ny] == 1) {
				board[nx][ny] = 0; //이미 검사한 땅은 0으로 바꿔줌
				DFS(nx, ny, board);
			}
		}
 	}
	
	public void solution(int[][] board) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(board[i][j] == 1) { // 땅인 지점을 중심으로 DFS 시작
					answer++; // 매번 DFS가 시작 될 때마다 새로운 섬
					board[i][j] = 0;
					DFS(i, j, board);
				}
			}
		}
	}
	
	public static void main(String[] args){
		Main main = new Main();
		Scanner sc = new Scanner(System.in);
		
		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();
			}
		}
		
		main.solution(board);
		
		System.out.println(answer);
		sc.close();
		return ;
	}
}