JAVA - [백준]2638 - 치즈

출처

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

문제

외부 공기와 2면이상 접촉한 치즈는 한시간만에 녹아 없어지게된다.

치즈가 나열되어있는 치즈 격자에서 모든 치즈가 녹아 없어지는 시간을 구하는 문제이다.

풀이

우선, 외부 공기라는 말이 중요하다. 필자는 단순히 공기와 치즈의 접촉면이 2면 이상이라면 녹는다고 이해하였지만, 사실은 달랐다. 모서리 면에 있는 공기가 외부 공기기 때문에 네모난 치즈들로 둘러 쌓인 네모난 공간 안에 치즈가 있다면, 그 치즈는 녹지 않는다.

(아래 예시에서 가운데 치즈는 녹지 않는다)

7 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 0 1 0 0
0 1 0 1 0 1 0
0 0 1 0 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0

녹은 치즈를 체크하기 전에 DFS를 통해 외부공기인지 판단해놓은 후 치즈가 녹는지 판단하는 과정을 거쳐야 한다.

그 다음 완전 탐색을 통해 치즈가 외부공기와 두면 이상 닿아있다면 녹는 치즈라는 표시를 해둔다.

표시가 끝나면 배열을 순회하며 표시해두었던 녹는 치즈를 일괄적으로 제거한다.

위의 과정들을 모든 치즈가 녹을때 까지 반복하여 총 반복한 횟수를 구하면 해결할 수 있다.

아래 코드를 보면 더 이해가 수월할 것이다.

코드

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

public class Main {
	static int N, M, answer;
	static int[][] world;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int cheezeCount;
    static boolean[][] visited;
    


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

        world = new int[N][M];
        answer = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				world[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        while (true) {
            visited = new boolean[N][M];
            checkAir(0, 0);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (world[i][j] == 1) {
                        checkMelt(i, j);
                    }
                }
            }
            int remainCheeze = 0;
            // 녹은치즈 제거
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (world[i][j] == 1) {
                        remainCheeze++;
                    }
                    if (world[i][j] == 2) {
                        world[i][j] = 0;
                    }
                }
            }
            answer++;
            if (remainCheeze == 0) {
                break;
            }
        }
        bw.write(answer + "\n");
        br.close();
        bw.flush();
        bw.close();
    }

    public static void checkMelt(int x, int y) {
        int count = 0;
        int nx, ny;
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (isValid(nx, ny) && world[nx][ny] == 3) {
                count++;
            }
        }
        // 녹는 치즈는 2로 표시 (나중에 일괄 제거)
        if (count >= 2) {
            world[x][y] = 2;
        }
    }

    //외부 공기와 접촉한 공기는 3으로 표시
    static void checkAir(int x, int y) {
        visited[x][y] = true;
        world[x][y] = 3;
    
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
    
            if (!isValid(nx, ny)) continue;
            if (visited[nx][ny] || world[nx][ny] == 1 || world[nx][ny] == 2) continue;
    
            checkAir(nx, ny);
        }
    }

    public static boolean isValid(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }

}