[백준 4963번] 섬의 개수 - java

문제 설명

1. 각각 테스트 케이스에서 섬의 크기를 입력받는데, 섬의 크기가 0, 0이면 종료되며 그 이전까지는 계속 입력받는다.

2. 해당 섬의 크기에 맞춰 1은 육지, 0은 바다로 지도를 만들어낸다.

3. 각 땅에서 상하좌우대각선 총 7방향으로 땅이 있으면 이동할 수 있다. 

3. 모든 테스트 케이스에 맞춰 총 섬의 개수를 return하면 된다.

풀이 과정

 1. 지뢰찾기와 비슷한 로직이다.

 2. 현재 위치를 기준으로 dfs를 사용하면 된다.

 3. 현재 위치 주변 7방향을 탐색하며 check해 주고, 물이면 나가고 땅이면 다시 dfs를 시도한다.

 4. for문을 돌려서 check하지 않은 땅들을 기준으로 값을 받아오면 된다.

 

코드

 

	import java.util.*;
	public class Main {
	public static int w = 1;
	public static int h = 1; // w, h의 값이 모두 0이면 끝난다. 처음에 값을 받기 위해 1로 세팅해둔다.
	public static int map[][];
	public static boolean check[][];
	static public ArrayList<Integer> ans = new ArrayList<Integer>(); // 정답을 미리 넣어둘 ans
	public static int X[] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 대각선까지 이동 가능하다. 이전에 만든 지뢰찾기와 비슷하게 진행된다.
	public static int Y[] = {-1, 0, 1, -1, 1, -1, 0, 1};
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	while(w!=0 && h!= 0) { // 0이 입력되면 끝
	w = sc.nextInt();
	h = sc.nextInt();
	if(w==0 && h==0) break; // 0이 입력되면 끝
	map = new int[h][w]; // h w로 지도와 체크 만들기
	check = new boolean[h][w];
	for(int i=0; i<h; i++) {
	for(int j=0; j<w; j++) {
	map[i][j] = sc.nextInt();
	}
	}
	int nowAns = 0;
	for(int i=0; i<h; i++) {
	for(int j=0; j<w; j++) {
	if(!check[i][j] && map[i][j]==1) { // 와본 적이 없는 곳 + 육지이면 새로운 섬이다. 따라서 섬의 개수가 하나 늘어난다.
	nowAns++; // 섬의 개수를 늘려준다.
	dfs(i, j); // 해당 섬에서 갈 수 있는 땅을 모두 체크하기 위한 dfs
	}
	}
	}
	ans.add(nowAns); // 각각 테스트 케이스 마다 nowAns를 구하면 섬의 개수들을 구할 수 있다.
	}
	ans.forEach(answer -> System.out.println(answer)); // 람다식 한번 써봄...이런걸 늘려가야겠다.
	}
	public static void dfs(int x, int y) {
	if(x<0 || x>=h || y<0 || y>=w) return; // map위치를 벗어나면 return
	if(check[x][y] || map[x][y]==0)return; // 육지가 아니거라, 이미 와본 곳이면 return
	check[x][y] = true; // 두 경우가 아니면 육지이고, main문의 섬의 시작점에서 갈 수 있는 곳이다. 즉 이미 존재하는 섬의 땅임.
	for(int i=0; i<8; i++) { // 이 땅에서 갈 수 있는 모든 위치를 탐색한다.
	dfs(x+X[i], y+Y[i]);
	}
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub