백준 2573번: 빙산

문제 설명

• https://www.acmicpc.net/problem/2573
• 빙산은 매 초 0과 접한 칸의 개수만큼 녹습니다. 빙산이 두 덩어리 이상으로 분리되거나 전부 다 녹는 시간을 구하는 문제입니다.

접근법

• BFS를 순회하는 중간에 빙산이 녹으면 안됩니다. 모든 BFS탐색이 끝난 뒤 일괄적으로 빙산이 녹아야 합니다.
  • 녹아야 할 빙산값을 담는 meltList를 만들었습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int R, C;
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, -1, 0, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		int[][] board = new int[R][C];
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int time = 0;
		while (true) {
			int cnt = 0;
			boolean[][] v = new boolean[R][C];
			for (int i = 1; i < R - 1; i++) {
				for (int j = 1; j < C - 1; j++) {
					if (board[i][j] == 0 || v[i][j])
						continue;
					cnt++; // 얼음이 몇덩이인지 계산하는 변수입니다.
					BFS(new int[] { i, j }, board, v);
				}
			}
			
            // 얼음이 2덩이 이상이면
			if (cnt >= 2) {
				System.out.println(time);
				break;
			}
            // 얼음이 0덩이면
			if (cnt == 0) {
				System.out.println(0);
				break;
			}
	
			// 이번에 녹아야 할 얼음들입니다. BFS 순회가 모두 끝난 뒤 얼음을 녹입니다.
			List<int[]> meltList = new LinkedList<int[]>();
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if (board[i][j] == 0)
						continue;
					int[] result = melt(i, j, board);
					if (result[2] == 0)
						continue;
					meltList.add(result);
				}
			}
			for (int i = 0; i < meltList.size(); i++) {
				int[] now = meltList.get(i);
				board[now[0]][now[1]] = Math.max(0, board[now[0]][now[1]] - now[2]);
			}

			time++;
		}

	}

	public static void BFS(int[] start, int[][] board, boolean[][] v) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		v[start[0]][start[1]] = true;
		while (!q.isEmpty()) {
			int[] now = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = now[0] + dx[d];
				int ny = now[1] + dy[d];
				if (0 <= nx && nx < R && 0 <= ny && ny < C && board[nx][ny] != 0 && !v[nx][ny]) {
					v[nx][ny] = true;
					q.add(new int[] { nx, ny });
				}
			}
		}
	}

	public static int[] melt(int x, int y, int[][] board) {
		int cnt = 0;
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (0 <= nx && nx < R && 0 <= ny && ny < C && board[nx][ny] == 0) {
				cnt++;
			}
		}
		return new int[] { x, y, cnt };
	}
}

기타

• Scanner보다 BufferedReader가 훨씬 빠릅니다.
  •