[백준] 2573번 : 빙산

문제

 

 

접근 방식

빙산을 매년 녹이면서 현재 빙산의 연결들이 끊어지지 않았는지 확인을 해주면 되는 간단한 문제다.

 

문제의 풀이 자체는 간단하게 떠올릴 수 있는데

PS는 항상 코드 작성이 문제다...

 

일단 입력을 받으면서 바다(0)가 아닌 1 ~ 10의 빙산들을 모두 큐에 넣어주었는데

이 때 시간을 같이 기록해줘야한다.

 

시간을 기록하는 이유는 만약 10개의 빙산 중 첫 번째 빙산이 녹았을 때

그 다음 빙산은 녹아버린 첫 번째 빙산을 바다로 취급하지 않아야 되는데

코드 상으로는 빙산이 하나씩 순서대로 녹아내리지만

실제로는 동시간대에 존재하는 모든 빙산이 한 번에 녹아야하기 때문이다.

 

즉, 같은 시간대의 빙산끼리는 서로에게 영향을 줄 수 없어야 하고

이를 위해서 큐에 넣을 객체는 빙산의 좌표와 시간대를 포함하게 했다.

 

이제 큐를 순회하면서 빙산의 가로세로 한 칸 범위에 바다가 존재할 때마다

빙산의 높이를 1씩 감소시켜준다.

 

녹아서 바다가 되지 않은 빙산들은 다시 큐에 넣고

다음 시간대에서 다시 녹게 해준다.

 

이제 마지막으로 해줄 것은 빙산이 끊어지지 않았는지 확인해주는 것인데

빙산을 모두 녹인 후에 시간대를 확인하는 것보단

해가 지날 때마다 녹지 않은 빙산을 순회하며 끊어지지 않았는지 확인해줬다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int[] dx = {1, -1, 0, 0};
		int[] dy = {0, 0, -1, 1};

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		Queue<Iceberg> icebergs = new LinkedList<>();

		int[][] north = new int[n][m];
		int[][] times = new int[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < m; j++) {
				int sea = Integer.parseInt(st.nextToken());
				times[i][j] = -1;
				north[i][j] = sea;

				// 빙산인 경우 큐에 넣어줌
				if (sea != 0) {
					icebergs.offer(new Iceberg(i, j, 0));
				}
			}
		}

		// 해가 바뀐지 확인하기 위한 변수
		int start = 0;

		while (!icebergs.isEmpty()) {
			Iceberg cur = icebergs.poll();
			int cx = cur.x;
			int cy = cur.y;
			int time = cur.time;
			times[cx][cy] = time;

			// 해가 바뀐 경우
			if (start != time) {
				start = time;

				int count = icebergs.size();

				Queue<Iceberg> queue = new LinkedList<>();
				boolean[][] isVisited = new boolean[n][m];

				queue.offer(cur);
				isVisited[cx][cy] = true;

				// 빙산이 끊기지 않았는지 확인
				while (!queue.isEmpty()) {
					Iceberg iceberg = queue.poll();
					int ix = iceberg.x;
					int iy = iceberg.y;

					for (int dir = 0; dir < 4; dir++) {
						int x = ix + dx[dir];
						int y = iy + dy[dir];

						if (x < 0 || x >= n || y < 0 || y >= m) continue;
						if (north[x][y] < 1 || isVisited[x][y]) continue;

						isVisited[x][y] = true;
						queue.offer(new Iceberg(x, y, 0));
						count--;
					}
				}

				// 끊겼으면 몇 해가 지났는지 출력하면서 종료
				if (count != 0) {
					System.out.println(time);
					return;
				}
			}

			// 상하좌우 확인하며 바다인 경우 빙산을 녹임
			for (int dir = 0; dir < 4; dir++) {
				int x = cx + dx[dir];
				int y = cy + dy[dir];

				if (x < 0 || x >= n || y < 0 || y >= m) continue;
				if (times[x][y] <= time && north[x][y] == 0 && north[cx][cy] > 0 && north[cx][cy] != 0)
					north[cx][cy]--;

			}

			cur.time++;

			// 빙산이 녹지 않은 경우에만 큐에 넣음
			if (north[cx][cy] != 0) {
				icebergs.offer(cur);
			}
			times[cx][cy] = cur.time;
		}

		System.out.println(0);
	}

	private static class Iceberg {
		int x;
		int y;
		int time;

		public Iceberg(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
	}
}