[백준] 2636. 치즈 - 골드5

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

2636번: 치즈

 

문제 요약

치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. 

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

 

문제 해결 아이디어

먼저 치즈를 입력받을 때, 치즈의 갯수를 세준다. 그래서 cheeseCnt가 0 초과일 동안, 반복문을 돌아 줄 것이다. 그렇게 하는 이유는 겉면 하나씩 bfs를 돌아 주기 위함이다. 하나의 bfs, 즉 안쪽에 있는 반복문은 한시간 동안의 겉면 하나에 대한 bfs이고 그 bfs가 끝나면 겉에 있는 반복문, 즉 아직 치즈가 살아있는지를 판단하여 시간 카운트를 늘려주고, 마지막 남은 치즈 갯수를 갱신해준다. 이건 모두 녹기 한 시간 전에 남아 있는 치즈조각을 구해야 하기 때문에 그냥 매 시간 갱신해 주는 것이다. 언제 끝날지 모르기 때문이다.

bfs를 도는 동안에는 특별한 건 없다. 네방향으로 치즈가 있는 부분은 0으로 바꾸고, 치즈 카운트를 하나 줄여 준다. 그렇게 해서 하나의 bfs를 다 돌면 한시간이 지난 것이다.

 

완성된 코드

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

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

		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		int[][] cheese = new int[r][c];
		int cheeseCnt = 0;
		for (int i = 0; i < r; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < c; j++) {
				cheese[i][j] = Integer.parseInt(st.nextToken());
				if (cheese[i][j] == 1)
					cheeseCnt++;
			}
		}

		int hour = 0;
		int lastCheese = 0;

		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };

		while (cheeseCnt > 0) { // 겉면 하나씩 탐색
			Queue<int[]> queue = new LinkedList<int[]>();
			boolean[][] visited = new boolean[r][c];
			queue.add(new int[] { 0, 0 });
			visited[0][0] = true;
			hour++;
			lastCheese = cheeseCnt;
			while (queue.size() > 0) {
				int[] current = queue.poll();

				for (int i = 0; i < 4; i++) {
					int nr = current[0] + dr[i];
					int nc = current[1] + dc[i];

					if (nr >= 0 && nr < r && nc >= 0 && nc < c && !visited[nr][nc]) {
						visited[nr][nc] = true;
						if (cheese[nr][nc] == 1) {
							cheese[nr][nc] = 0;
							cheeseCnt--;
						} else
							queue.offer(new int[] { nr, nc });
					}
				}
			}
		}

		System.out.println(hour);
		System.out.println(lastCheese);
	}
}