[Java] 백준 2573번: 빙산

[문제 바로 가기] - 빙산

문제에서 요구하는 대로 풀이하면 된다.
풀고 나니 그렇게 복잡한 문제가 아니였는데 구현 과정에서 시간이 꽤나 걸렸었다.😅

💡 아이디어

먼저 빙산의 높이를 저장할 2차원 배열 iceberg과 물이 아닌 빙산의 높이만 저장할 List icebergs를 선언한다.

1. 분리 확인 로직 : isSeperate()

어차피 빙산은 위아래 행과 양 끝 열에는 존재하지 않으므로 1부터 N-1, M-1까지 돌면서 BFS 탐색을 한다. 이때, 덩어리 별로 count++를 하는데 count가 2 이상일 경우 분리되었다는 뜻이므로 true를 반환한다.

2. 빙산이 분리되지 않았는데 다 녹았을 경우

isSerperate()가 false인데 icebergs에 있는 (높이가 0이 아닌, 즉 물이 아닌) 빙산이 하나도 없을 경우 0을 출력한다.

3. 빙산 녹이는 로직 : meltIceberg()

iceberg에 들어있는 빙산을 기준으로 4방향 탐색하면서 근처에 물(0)의 개수를 센다. 현재 빙산의 높이가 물의 개수보다 클 경우에는 물의 개수를 빼주고 icebergs에 다시 넣어준다. 또한 물의 개수보다 작을 경우에는 해당 빙산의 높이를 0으로 만들어준다.

---

풀이

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

/**
 * 백준 2573번 빙산
 * - 두 덩어리 이상으로 분리되는지 확인 : Bfs 탐색
 * - 아직 녹지 않은 빙산 List에 넣어서 관리
 */

public class Main {
	public static int[][] deltas = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
	public static int N, M, iceberg[][];
	public static List<int[]> icebergs;
	public static boolean[][] visited;
	
	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()); // 3 <= N <= 300
		M = Integer.parseInt(st.nextToken()); // 3 <= M <= 300
		
		iceberg = new int[N][M]; // 빙산 높이 저장할 배열
		icebergs = new ArrayList<>(); // 높이가 0이 아닌 빙산 저장할 리스트
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				iceberg[i][j] = Integer.parseInt(st.nextToken());

				if (iceberg[i][j] > 0) icebergs.add(new int[] {i, j});
			}
		}
		
		int year = 0;
		
		while (true) {
			visited = new boolean[N][M];
			
			// 두 덩어리 이상으로 분리되는지 확인
			if (isSeperate()) {
				System.out.println(year);
				break;
			}
			
			// 빙산이 다 녹을 때까지 분리되지 않았을 경우
			if (icebergs.isEmpty()) {
				System.out.println(0);
				break;
			}
			
			meltIceberg();
			year++;			
		}
	}
	
	// 빙산 녹이기
	public static void meltIceberg() {
		List<int []> newIcebergs = new ArrayList<>();
		int[][] newIceberg = copyArray(iceberg);
		
		for (int[] ib : icebergs) {
			int x = ib[0];
			int y = ib[1];
			
			int waterCount = 0;

            for (int i = 0; i < 4; i++) {
                int dx = x + deltas[i][0];
                int dy = y + deltas[i][1];

                if (dx >= 0 && dy >= 0 && dx < N && dy < M && iceberg[dx][dy] == 0) waterCount++;
            }
            
            if (newIceberg[x][y] > waterCount) {
            	newIceberg[x][y] -= waterCount;
                newIcebergs.add(new int[]{x, y});
            } else newIceberg[x][y] = 0;
		}

		// 배열, 리스트 복사
        icebergs = newIcebergs;
        iceberg = newIceberg;
	}
	
	
	public static int[][] copyArray(int[][] original) {
		int[][] newArr = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			newArr[i] = Arrays.copyOf(original[i], original[i].length);
		}
		
		return newArr;
	}
	
	// 두 덩어리 이상으로 분리되는지 확인하는 메소드
	public static boolean isSeperate() {
		int count = 0;
		
		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < M - 1; j++) {
				if (iceberg[i][j] != 0 && !visited[i][j]) {
					bfs(i, j);
					count++;
				}
				if (count >= 2) return true;
			}
		}
		
		return false;
	}
	
	// 연결된 덩어리 탐색 메소드
	public static void bfs(int x, int y) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {x, y});
		visited[x][y] = true;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			
			for (int i = 0; i < 4; i++) {
				int dx = cur[0] + deltas[i][0];
				int dy = cur[1] + deltas[i][1];
				
				if (dx >= 1 && dy >= 1 && dx < N - 1 && dy < M - 1 && iceberg[dx][dy] != 0 && !visited[dx][dy]) {
					visited[dx][dy] = true;
					queue.add(new int[] {dx, dy});
				}
			}
		}
	}
}