[백준] 2573번 빙산 자바

문제 (골드4)

 

2573번: 빙산

 

 

 

문제 풀이

 

✔️ 사용변수

빙산의 높이를 입력받을 2차원 배열:  int[][] ice

1년 녹는 빙산의 개수를 받을 2차원 배열:  int[][] melt

빙산이 분리되는 것을 확인하기 위해 DFS를 실행할 2차원 배열: boolean[][] visited

반복하며 상하좌우로 움직이기 위한 1차원 배열: int[] moveX, int[] moveY

 

✔️ afterYear() 알고리즘

1. ice배열을 순회하며 0이상의 값을 가진 경우(빙산 존재),

   상하좌우를 확인하여 바다의 개수만큼(값이 0인 개수) 해당 melt배열의 값을 증가

2. ice배열 순회하며 melt배열 값을 빼준다. ice가 마이너스 값을 가질 경우 0으로 삽입

3. 다시 melt배열은 초기화 시켜주고 반복한다.

 

✔️ isDivide() 알고리즘

1. ice배열을 순회하며 0이상의 값을 가진경우 그 행과 열을 가지고 DFS실행

   이때, visited배열이 true가 아니여야 한다. 빙산이 쪼개지는 경우를 세기 위해 다시 반복하지 않기 위해 애초에 DFS실행 할 때 visited를 검사하고 실행!

2. DFS실행 횟수를 count변수에 담아 빙산의 덩어리 횟수 세고 경우에 따라 함수 반환값을 정한다.

3. count가 0일 경우에는 빙산이 0이상인 경우가 없으므로 빙산이 다 녹았다는 뜻

 

 

 

소스 코드

 

public class b_2573 {

	static int[] moveX = {-1, 1, 0, 0};	//상하좌우
	static int[] moveY = {0, 0, -1, 1};
	static int N, M;
	static int[][] ice;
	static boolean[][] visited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int answer, count = 0;
		N = sc.nextInt();
		M = sc.nextInt();
		ice = new int[N][M];
		
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				ice[i][j] = sc.nextInt();
		
		while(true) {
			visited = new boolean[N][M];
			afterYear();
			count++;
			answer = isDivide();
			if(answer != -1)
				break;
		}
		if(answer == 0)
			System.out.println("0");
		else
			System.out.println(count);
		sc.close();		
	}
	
	public static void afterYear() {
		int[][] melt = new int[N][M];		//녹을 빙산 개수
		
		for(int x = 0; x < N; x++) {
			for(int y = 0; y < M; y++) {
				if(ice[x][y] > 0) {
					for(int k = 0; k < 4; k++) {
						int nextX = x + moveX[k];
						int nextY = y + moveY[k];
						if(nextX >= 0 && nextX <= N && nextY >= 0 && nextY <= M && ice[nextX][nextY]==0)
							melt[x][y] += 1;
					}
				}
			}
		}

		for(int x = 0; x < N; x++) {
			for(int y = 0; y < M; y++) {
				if(melt[x][y] > 0) {
					ice[x][y] -= melt[x][y];
					if(ice[x][y] < 0)
						ice[x][y] = 0;
				}
			}
		}
		
		/*System.out.println("1년 후의 빙산");
		for(int x = 0; x < N; x++) {
			for(int y = 0; y < M; y++) 
				System.out.print(ice[x][y] +" ");
			System.out.println();
		}*/
	}
	
	public static void DFS(int x, int y) {
		if(visited[x][y] == true || ice[x][y] == 0)
			return;
		
		visited[x][y] = true;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + moveX[i];
			int ny = y + moveY[i];
			if(nx >= 0 && nx <= N && ny >=0 && ny <= M)
				DFS(nx, ny);
		}
	}
	
	public static int isDivide() {
		int count = 0;
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				if(ice[i][j] > 0 && visited[i][j] == false) {
					DFS(i, j);
					count++;
				}

		if(count > 1)
			return count;			//2개 이상으로 분리됨
		else if(count == 0)			//아예 순회를 하지 않음. 고로 빙산이 다 녹았다는 뜻
			return 0;
		else
			return -1;			//아직 한 덩이의 빙산으로 남아있음 
	}

}