2573: 빙산 (구현)

풀이

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = { -1, 1, 0, 0 }; // 상하좌우
	static int[] dy = { 0, 0, -1, 1 }; // 상하좌우

	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());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M];
		Queue<Integer> queue = new LinkedList<Integer>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] != 0) {
					queue.offer(i);
					queue.offer(j);

				}
			}
		}

		int year = 0;
		boolean flag = false;
		while (!queue.isEmpty()) {
			// 덩어리 개수 체크
			int n = queue.size() / 2;
			visited = new boolean[N][M];
			int cnt = 0;

			while (n > 0) {
				int x = queue.poll();
				int y = queue.poll();
				queue.offer(x);
				queue.offer(y);
				if (!visited[x][y]) {
					cnt++;
					checkIce(x, y);
				}
				n--;
			}

			if (cnt >= 2) {
				flag = true;
				break;
			}
			// 빙하높이 감소
			year++;
			n = queue.size() / 2;
			while (n > 0) {
				int x = queue.poll();
				int y = queue.poll();
				for (int k = 0; k < 4; k++) {
					int nx = x + dx[k];
					int ny = y + dy[k];
					if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny]) {
						if (map[x][y] > 0)
							map[x][y]--;
					}
				}
				if (map[x][y] != 0) {
					queue.offer(x);
					queue.offer(y);
				}
				n--;
			}
		}
		if (flag)
			System.out.println(year);
		else
			System.out.println(0);

	}

	static void checkIce(int x, int y) {
		if (visited[x][y]) {
			return;
		}
		visited[x][y] = true;
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] != 0 && !visited[nx][ny]) {
				checkIce(nx, ny);
			}
		}
	}
}