2573. 빙산

롯데이커머스의 코딩테스트를 본 후 비슷한 문제를 찾아보았다. 

오답노트랄까...

먼저 문제를 해결하고자 했던 내가 착각했던 부분..!!!이 있었다.

while문의 반복을 빠져나오기 위한 조건을 생각했고, 최대 빙하의 높이가 10까지라고 제시되었기에 while문을 10번까지만.. 돌렸다.

아차!!! 빙하가 10이라고 해서 10번안에 다 녹는게 아니지!!! 안에 있는 빙하는 겉의 빙하가 녹기전에는 절대 녹지 않기 때문이다.

 

그리고 주의해야 할 점은 배열을 순차적으로 빙하가 녹을 것을 계산하고, 바로 녹임을 처리하면 그 다음 빙하에서 0의 값을 확인할 때 오차값이 발생하여 정확한 계산의 방식이 될 수 없다는 것이다.

따라서, 배열 복사를 진행했다.

나의 풀이는 아래와 같다.

 

package baekjoon;

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

public class B_2573_빙산 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int h = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		int[][] arr = new int[h][w];
		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < w; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
		int[][] map = new int[h][w];// 빙하 계산 전 복사할 배열
		int time = 0; // 빙하를 분리하는데 걸리는 시간

		while (true) {
			int cnt = 0; // 빙하의 분리 개수 -> 연산의 끝을 정함
			time++; // 시간 경과

			// 배열 복사
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					map[i][j] = arr[i][j];
				}
			}
			// 빙하 녹기
			for (int i = 1; i < h - 1; i++) {
				for (int j = 1; j < w - 1; j++) {
					if (map[i][j] != 0) {
						int zeroCnt = 0; // 녹아내리는 속도 -> 주위의 호수 개수
						for (int d = 0; d < 4; d++) {
							int y = i + dir[d][0];
							int x = j + dir[d][1];
							if (y < 0 || x < 0 || y >= h || x >= w)
								continue;
							if (map[y][x] == 0) {
								zeroCnt++;
							}
						}
						// 빙하 녹이기
						arr[i][j] = arr[i][j] - zeroCnt < 0 ? 0 : arr[i][j] - zeroCnt;
					}
				}
			}

			// 분리되었는지 확인
			boolean[][] visited = new boolean[h][w];
			cnt = 0;
			for (int i = 1; i < h - 1; i++) {
				for (int j = 1; j < w - 1; j++) {
					if (arr[i][j] != 0 && !visited[i][j]) {
						bfs(i, j, h, w, arr, dir, visited);
						cnt++;
					}
				}
			}
			if (cnt >= 2) { // 분리 성공
				break;
			} else if (cnt == 0) { // 빙하가 모두 사라졌을 경우 -> 연산 끝
				time = 0;
				break;
			}
		}
		System.out.println(time);
	}

	private static void bfs(int y, int x, int h, int w, int[][] arr, int[][] dir, boolean[][] visited) {
		Queue<Node> q = new LinkedList<>();
		visited[y][x] = true;
		q.offer(new Node(y, x));
		while (!q.isEmpty()) {
			Node now = q.poll();
			y = now.y;
			x = now.x;
			for (int i = 0; i < 4; i++) {
				int my = y + dir[i][0];
				int mx = x + dir[i][1];
				if (mx < 0 || my < 0 || my >= h || mx >= w || visited[my][mx])
					continue;
				if (arr[my][mx] == 0)
					continue;
				visited[my][mx] = true;
				q.offer(new Node(my, mx));
			}
		}
	}

	static class Node {
		int y, x;

		public Node(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

	}
}