[백준 / JAVA] 2573. 빙산

https://www.acmicpc.net/problem/2573

2573번: 빙산

 

---

💻 풀이 결과

💯 최종 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node {
	int r, c;

	Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] map = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		Queue<Node> queue = new LinkedList<>();
		boolean[][] visited;
		boolean[][] flag; // 빙산이 녹을 때 0이 된 것을 체크해주기 위해 (동시에 녹는 것 방지)
		int[] dr = { 0, 0, -1, 1 };
		int[] dc = { -1, 1, 0, 0 };

		int year = 0;
		Loop1: while (true) {
			// 빙산 분리된 덩어리 갯수 세기
			int cnt = 0;
			visited = new boolean[N][M];
			for (int i = 1; i < N - 1; i++) {
				for (int j = 1; j < M - 1; j++) {
					// 방문하지 않은 빙산 찾았다.
					if (!visited[i][j] && map[i][j] > 0) {
						queue.add(new Node(i, j));
						visited[i][j] = true;
						cnt++;
						// 두 덩어리 이상으로 분리되었다.
						if (cnt > 1) {
							System.out.println(year); // 최초의 시간(년) 출력
							break Loop1;
						}

						while (!queue.isEmpty()) {
							Node curr = queue.poll();

							for (int d = 0; d < 4; d++) {
								int nr = curr.r + dr[d];
								int nc = curr.c + dc[d];

								if (!visited[nr][nc] && map[nr][nc] > 0) {
									queue.add(new Node(nr, nc));
									visited[nr][nc] = true;
								}
							}
						}
					}
				}
			} // 빙산 덩어리 갯수 세기 끝

			// 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력
			if (cnt == 0) {
				System.out.println(0);
				break;
			}

			year++; // +1년 후

			// 빙산 녹이기
			flag = new boolean[N][M];
			for (int i = 1; i < N - 1; i++) {
				for (int j = 1; j < M - 1; j++) {
					// 빙산을 찾았다.
					if (map[i][j] > 0) {
						// 4방 탐색
						for (int d = 0; d < 4; d++) {
							int nr = i + dr[d];
							int nc = j + dc[d];

							// 바다가 있다면 빙산의 높이 -1 녹이자
							if (!flag[nr][nc] && map[nr][nc] == 0) {
								map[i][j]--;

								// 다 녹았다. -> 4방 탐색 그만해도 됨
								if (map[i][j] == 0) {
									flag[i][j] = true; // 동시에 녹는 것을 방지하기 위해
									break;
								}
							}
						}
					}
				}
			} // 전체 빙산 녹이기 1회 끝
		} // Loop1 끝
	}
}

💢 틀린 이유

• 4방향의 빙산이 같은 시간에 동시에 녹는 것을 고려하지 않았서 틀렸다.
• 해결하기 위해 flag 배열을 추가해 주었다.

💬 풀이 과정

• BFS를 돌리면서 빙산을 녹인다.
• 동시에 녹는 것을 방지하기 위해서 flag 배열을 생성한다.
• flag가 false이고 바다가 접해있다면 map을 -1 한다.
• 한 사이클에서 빙산이 녹아 0이 된 경우는 flag를 true로 표시해 준다.
• cnt가 2가 되는 순간 빙산이 분리가 된 것이므로 year 출력한다.

💡 깨달은 점

1. BFS에서 동시에 일어나는 사건 처리

• 동시에 진행이 되는 경우를 체크해 주는 데 유의해야 한다.