[PS] 인프런 강의 - DFS 11. 섬나라 아일랜드

 

문제

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

풀이

 

대각선 까지 고려해야 하므로 좌표 이동의 경우의 수가 다음과 같이 늘어난다.

int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

 

map 배열에 입력값을 모두 저장한 뒤, 이중 반복문으로 쭉 탐색을 한다.

탐색하는 좌표의 값이 1이면 섬 개수를 카운트 +1 하고, 값을 0으로 바꾼뒤 DFS 함수를 호출한다. DFS함수에서는 재귀호출을 사용해 섬의 모든 값을 0으로 바꾼다. 그러면 호출이 모두 끝나고이중 반복문으로 돌아왔을 때 다른 섬을 탐색할 수 있게 된다.

 

코드

import java.util.Scanner;

public class Main {
	static int n, m;
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	static int[][] map;
	static int answer;
	
	public static void DFS(int x, int y) {
        for(int i=0; i<8; i++) {
    		int nx = x + dx[i];
    		int ny = y + dy[i];
    		
    		if(nx>=0 && nx<n && ny>=0 && ny<n && map[nx][ny] == 1) {
    			map[nx][ny] = 0;
    			DFS(nx, ny); //해당 섬의 값 모두 0으로 만들때까지 반복
    		}
        }
	}
 
	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        n = in.nextInt();
                
        map = new int[n][n];
        for(int i=0; i<n; i++) {
        	for(int j=0; j<n; j++) {
        		map[i][j] = in.nextInt();
        	}
        }
        
        for(int i=0; i<n; i++) {
        	for(int j=0; j<n; j++) {
        		if(map[i][j] == 1) {
        			answer++;
        			map[i][j] = 0; //출발
        			DFS(i, j);
        		}
        	}
        }   
        System.out.println(answer);
        
    }
}