백준 2573 빙산

백준 2573 빙산

1. 문제 링크

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

2573번: 빙산

 

2. 문제 해결에 대한 아이디어

1. 1년이 지날 때마다 바다와 맞닿은 빙산이 최대 4까지 그 크기가 줄어든다.

2. 이때, 현재의 맵에 바로 반영하는 게 아니라, 임시 맵(copyBoard)을 만들어 다음 해의 빙산의 크기를 기록한다.

3. 나누는 이유는 현재 맵에 반영할 경우, 원래보다 맞닿는 면이 많아져 빙산이 더 녹게 계산될 수 있기 때문이다.

4. 빙산이 두 개로 나뉘어졌을때 종료해야 하므로, 매 해 빙산에서 BFS를 통해 나뉜 개수를 카운트한다.

5. 이때 BFS를 수행한 횟수를 저장하여 2개 이상으로 나뉘어져있는지 혹은 다 녹았는지를 판단한다.

6. 나뉘지도 않고 다 녹지도 않았으면 빙산을 녹인다.

 

3. 코드

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

public class Main {
	static int N, M;
	static int[][] board;
	static int[][] copyBoard;
	static boolean[][] visit; // 매번 나뉘어졌는지 체크
	static int day = 0;
	static int iceCount = 0;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static Queue<Pair> devideQ = new LinkedList<>(); //

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");

		N = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]);

		board = new int[N][M];
		copyBoard = new int[N][M];
		visit = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < M; j++) {
				board[i][j] = copyBoard[i][j] = Integer.parseInt(line[j]);

			}
		}

		while (true) {
			int devideCount = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] != 0 && !visit[i][j]) {
						devideQ.add(new Pair(i, j));
						divideChecker();
						devideCount++;
					}
				}
			}

			// 나뉘어진 갯수가 2 이상이면 끝
			if (devideCount >= 2)
				break;
			// 나뉘어진 갯수가 없으면 빙산이 없다는 것
			else if (devideCount < 1) {
				System.out.println(0);
				return;
			}

			day++;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] != 0) {
						melt(i, j);
					}
				}
			}

			// 다음 로직을 위해 초기화
			reset();

		}

		System.out.println(day);
		br.close();
	}

	static void melt(int y, int x) {

		int waterCount = 0;

		for (int i = 0; i < 4; i++) {
			int yy = y + dirY[i];
			int xx = x + dirX[i];

			if (board[yy][xx] == 0)
				waterCount++;

		}
		int nextStatus = board[y][x] - waterCount;
		copyBoard[y][x] = nextStatus >= 0 ? nextStatus : 0;

	}

	static void divideChecker() {
		while (!devideQ.isEmpty()) {
			Pair now = devideQ.poll();
			int y = now.y;
			int x = now.x;
			visit[y][x] = true;

			for (int i = 0; i < 4; i++) {
				int yy = y + dirY[i];
				int xx = x + dirX[i];

				if (yy < 0 || xx < 0 || yy >= N || xx >= M || visit[yy][xx] || board[yy][xx] == 0)
					continue;

				visit[yy][xx] = true;
				devideQ.add(new Pair(yy, xx));
			}
		}
	}

	static void reset() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = copyBoard[i][j]; // 녹은 빙산의 상태값을 원래 보드로 가져옴
			}
		}
		visit = new boolean[N][M]; // 디바이드 체크를 위한 방문 배열 초기화
		devideQ.clear();
	}

}

class Pair {
	int y, x;

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

}

 

4. 채점 결과

 

5. 느낀 점

1. C++로 할 땐 이차원 벡터를 사용해서, 배열 간 복사를 '=' 하나로 끝냈는데 자바는 배열로 하는 게 더 편하더라.

2. 자바 이차원 배열에 대한 deep copy 방법을 찾아보니 하나씩 복사하는게 제일 속편 해서 그렇게 하기로 했다.

3. 빙산의 다음 상태를 다른 배열에 기록하고 후에 복사, 방문 배열 초기화 등이 중요했다.