[인프런 자바/java] 13. 섬나라 아일랜드 _디버깅의 눈물

 

 

체크 포인트

 

1. DFS(깊이 우선 탐색)을 이용하는 문제

-섬나라 아일랜드 상에 존재하는 '전체 섬의 개수'를 구하는 문제

-DFS를 이용한 완전 탐색으로 해결하도록 하였다.

 

2.상,하,좌,우 + 대각선 탐색

-일반적인 DFS를 이용해 푸는 문제라 딱히 특별한 점은 없었다.

 

	// 상,하,좌,우,대각선 방향 탐색을 위한 x,y
	static int[] dx = {0,0,-1,1,-1,-1,1,1};
	static int[] dy = {1,-1,0,0,-1,1,-1,1};

 

-다른 문제와 차이점은 섬 탐색 시 기준점을 기준으로 상,하,좌,우뿐만 아니라, 대각선 부분도 탐색하는 부분이 존재했다.

 

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	// 정사각형 변의 길이 
	static int N;
	// 육지와 바다를 표시해주는 지도 배열 
	static int[][] map;
	// 해당 위치에 방문여부를 담는 배열 
	static boolean[][] visited;
	
	// 상,하,좌,우,대각선 방향 탐색을 위한 x,y
	static int[] dx = {0,0,-1,1,-1,-1,1,1};
	static int[] dy = {1,-1,0,0,-1,1,-1,1};
	
	// 섬 개수 카운트 변수 
	static int count;

	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	// 정사각형 변의 길이 
    	N = Integer.parseInt(st.nextToken());
    	
    	// 지도 배열 초기화 
    	map = new int [N][N];
    	// 방문 배열 초기화 
    	visited = new boolean[N][N];
    	
    	// 지도 내 섬의 값 입력 
    	for(int i=0; i<N; i++) {
    		
    		st = new StringTokenizer(br.readLine(), " ");
    		
    		for(int j=0; j<N; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	/*
    	for(int i=0; i<N; i++) {
    		
    		for(int j=0; j<N; j++) {
    			if(j==N-1) {
    				System.out.println(map[i][j] + " ");
    			}
    			else {
    				System.out.print(map[i][j] + " ");
    			}
    		}
    	}
    	*/
    	
    	// DFS 탐색 시작 부분 
    	for(int i=0; i<N; i++) {
    		
    		for(int j=0; j<N; j++) {
    			// 해당 위치에 방문한 적이 없고, 해당 위치가 육지라면, 
    			if(!visited[i][j] && map[i][j] == 1) {
    				DFS(i,j);
    				// 섬 총 개수 증가 처리 
    				count++;
    			}
    		}
    	}
    	
    	System.out.println(count);
    }
    
    static void DFS(int x, int y) {
    	// 방문 처리 
    	visited[x][y] = true;
    	
    	// 상,하,좌,우,대각선 탐색 시작 
    	for(int i=0; i<8; i++) {
    		
    		int nx = x + dx[i];
    		
    		int ny = y + dy[i];
    		
    		// 새로운 nx, ny가 지도 배열 내 위치하고, 
    		if(nx>=0 && ny>=0 && nx<N && ny<N) {
    			// 해당 위치가 섬이고, 방문한 적이 없다면, 
    			if(map[nx][ny]==1 && !visited[nx][ny]) {
    				// DFS탐색 시작 
    				DFS(nx,ny);
    				
    			}
    		}
    		
    	}
    	
    	
    }
    

} // end of Main