[백준 - 골드] 2638. 치즈

이번 주의 문제

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

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

생각해본 풀이

1. 외부 공기 / 내부 공기를 어떻게 나눌 수 있을까?
2. 0, 0은 무조건 외부 공기(외곽은 치즈가 없다고 나옴)
3. 0,0부터 bfs 또는 dfs를 활용하여 외부 공기를 체크하는 로직을 통해 치즈를 없애면 되겠다.

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

public class 치즈_2638 {

	static int[][] paper;
	static int N, M;
	
	static boolean[][] visit;

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

	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());
		M = Integer.parseInt(st.nextToken());

		paper = new int[N][M]; // 모눈종이

		int count = 0;

		for (int r = 0; r < N; r++) {
			st = new StringTokenizer(br.readLine());

			for (int c = 0; c < M; c++) {
				paper[r][c] = Integer.parseInt(st.nextToken());

				if (paper[r][c] == 1) count++; // 치즈크기
			}
		} // 입력
		

		int time = 0;

		// 치즈가 없어질 때까지
		while (count != 0) {
			
			visit = new boolean[N][M]; //방문 초기화
			dfs(0, 0); //외부공기

			for (int r = 0; r < N; r++) {
				for (int c = 0; c < M; c++) {
					
					if(paper[r][c] == 1 && isMelting(r, c)) {
						paper[r][c] = 0;
						count--;
					}
				}
			}
			
			time++;
		}
		
		System.out.println(time);
	}
	
	private static void dfs(int r, int c) {
		visit[r][c] = true;
		paper[r][c] = 2; //외부공기
		
		for(int d = 0; d < 4; d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= M || paper[nr][nc] == 1 || visit[nr][nc]) continue;
			
			dfs(nr, nc);
		}
	}

	//녹을 수 있는 치즈 가장자리인가
	private static boolean isMelting(int r, int c) {
		
		int count = 0;
		
		for(int d = 0; d < 4; d++) {
			
			int nr = r + dr[d];
			int nc = c + dc[d];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
			
			if(paper[nr][nc] == 2) count++;
		}
		
		if(count >= 2) return true;
		
		return false;
	}
}