백준 2573 빙산 (Java)

1. 문제 링크

2573번: 빙산

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 입력받고 종료 조건이 될 때까지 반복문을 돈다.
2. 처음에 덩어리 개수를 구하는데 0이거나 2보다 커지면 탈출한다.
3. 그리고 빙산 기준으로 사방탐색을 해서 바다와 닿은 면적을 계산한다. 3-1. 바로 녹이지 않고 큐에 담아둔다. 3-2. 모든 빙산을 다 녹였다면 큐에 넣어둔 녹은 빙산을 map에 적용한다.
4. 시간을 증가하고 반복문을 계속한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] split = br.readLine().split(" ");
		int N = Integer.parseInt(split[0]);
		int M = Integer.parseInt(split[1]);
		int[][] map = new int[N][M];
		int result = 0;
		int cnt = 0;
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				int temp = Integer.parseInt(split[j]);
				map[i][j] = temp;
				if(temp != 0) {
					cnt++; //빙산 개수
				}
			}
		}
		
		int dx[] = {0,0,-1,1};
		int dy[] = {-1,1,0,0};
		int temp;
		Queue<int[]> queue = new ArrayDeque<>();
 		while(true) {
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++){
					temp = 0;
					if(map[i][j]!= 0) {
						for(int d=0;d<4;d++) {
							int X = i+dx[d];
							int Y = j+dy[d];
							if(X<0 || X>=N || Y<0 || Y>=M || map[X][Y] != 0) {
								continue;
							}
							temp++;
						}
						int now = map[i][j] - temp; //녹고 남은 빙산
						if(now <= 0) {
							queue.offer(new int[] {i, j, 0});
							cnt--;
						}
						else {
							queue.offer(new int[] {i, j, now});
						}
					}
				}
			}
			while(!queue.isEmpty()) {
				int[] now = queue.poll();
				if(now[2] == 0) {
					map[now[0]][now[1]] = 0;
				}
				else {
					map[now[0]][now[1]] = now[2];
				}
			}
			if(cnt == 0) {
				break;
			}
			result++;
		}	
		System.out.println(result);
	}
}