N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.
섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
Image1.jpg
만약 위와 같다면 섬의 개수는 5개입니다.
입력
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
두 번째 줄부터 격자판 정보가 주어진다.
public class Island {
static int[][] arr, check;
static int[][] dir = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
static int input1, answer = 0;
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
input1 = in.nextInt();
arr = new int[input1+1][input1+1];
check = new int[input1+1][input1+1];
for(int i=1; i<=input1; i++){
for(int j=1; j<=input1; j++){
arr[i][j] = in.nextInt();
}
}
solution(1,1);
System.out.println(answer);
}
public static void solution(int x, int y){
for(int i=1; i<=input1; i++){
for(int j=1; j<=input1; j++){
if(arr[i][j] != 0 && check[i][j] != 1){
dfs(i,j);
answer++;
}
}
}
}
public static void dfs(int x, int y){
if(arr[x][y] == 0 || check[x][y] == 1)return;
check[x][y] = 1;
for(int[] direct : dir){
int nx = x+direct[0];
int ny = y+direct[1];
if(nx>0 && nx<=input1 && ny>0 && ny<=input1){
dfs(nx, ny);
check[nx][ny] = 1;
}
}
}
}
전에 풀었던 동일한 아일랜드 문제이다. 강의를 보니 DFS로도 풀수 있다고 해서 DFS로 풀어봤다. 문제를 처음 봤을 때도 DFS로 풀지 BFS로 풀어야할지 고민했었는데 그 생각이 맞았었나보다. 그래도 다행히 BFS로 풀어봐서 문제를 이해한 상태로 풀어서 그런지 DFS도 금방 풀었다.
DFS에서 중요한 부분은 check[][] 배열을 언제 체크해주냐에 따라 정답이 달라지므로 디버그를 찍어보면서 이해하는게 좋을거 같다!