섬나라아일랜드

코드

class 섬나라아일랜드 {
	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};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1) {
				board[nx][ny] = 0;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 0;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{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}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

---

결과

===1번 섬지우기===
 0  0  0  0  0  1  0 
 0  0  0  0  1  1  0 
 0  0  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 

===2번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  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 

===3번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 1  1  0  0  0  0  0 
 1  0  0  0  0  0  0 
 1  0  1  0  0  0  0 

===4번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  1  0  0  0  0 

===5번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 

5

---

주어진 2차원 배열(지도)에 1 표기가 섬이다. 섬은 상하좌우 좌상우상좌하우하 이렇게 8방향으로 연결되어 있다.

 

solution은 지도를 순회하여 섬을 탐색한다.

DFS는 섬을 지도에서 소거한다. 이렇게 되면 자연스럽게 solution이 다시 순회를 시작해도 같은 섬 중복이 날수가 없다.

 

여기서는 1이면 섬으로 판단한다. 그래서 가시성을 위해 지워진 섬을 99로 변경해 어떻게 동작하는지 좀 더 명확하게 볼 수 있다.

 

코드

class 섬나라아일랜드 {
	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};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1 ) {
				board[nx][ny] = 99;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 99;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{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}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

---

결과

===1번 섬지우기===
99 99  0  0  0  1  0 
 0 99 99  0  1  1  0 
 0 99  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 

===2번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  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 

===3번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
 1  1  0 99 99  0  0 
 1  0  0  0 99  0  0 
 1  0  1  0 99  0  0 

===4번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0  1  0 99  0  0 

===5번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0 99  0 99  0  0 

5

---