[백준] 2638번: 치즈 (Java)

문제

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

난이도 : 골드3

알고리즘 : 그래프 탐색, 구현

---

풀이 과정

세로 길이 N, 가로 길이 M의 모눈종이에 치즈가 올려져 있고, 치즈가 없는 공간에는 공기가 있다. 치즈는 치즈 외부의 공기와 2변 이상이 접촉하면 1시간만에 녹아버린다. 주어진 치즈가 모두 녹아 없어지는데 걸리는 시간을 구해야 한다. 

 

치즈가 녹는 과정을 구현하려면 매 시간마다 모든 치즈에 대해 외부 공기와 접촉했는지 여부를 검사해야 한다. 이 때, 먼저 고려해야 할 것은 치즈 내부의 공간은 외부 공기와 접촉하지 않은 것으로 가정하는 조건이다. 이 조건 때문에 무작정 치즈에 인접한 공기의 개수를 세어서는 문제를 해결할 수 없었다.

 

한편, 모눈종이의 맨 가장자리는 치즈가 놓이지 않으므로, 맨 가장자리는 항상 외부 공기라고 할 수 있다. 그렇기 때문에 맨 가장자리에서 인접한 공기를 찾는 그래프 탐색을 통해 외부 공기를 찾을 수 있었다. 이 때 탐색되지 않은 공기는 외부 공기와 연결되지 않았으므로, 치즈 내부의 공간이라고 판단하면 된다. 한 번의 BFS 또는 DFS를 통해 구현할 수 있는데, 나의 경우는 BFS를 사용하였다.

 

이렇게 외부 공기를 정의하고 나면 치즈가 있는 모든 칸을 돌며 인접한 외부 공기가 2개 이상인 경우를 찾아서 해당 칸을 공기로 바꿔주기만 하면 된다. 이 과정을 더 이상 녹일 치즈가 없어질 때까지 반복하면 문제를 해결할 수 있다.

 

---

코드

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] graph = new int[n][m];
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int time = 0;
        while(true){
            boolean[][] isAir = bfs(graph);
            int cnt = melt(graph, isAir);
            if(cnt == 0) break;
            time++;
        }

        System.out.print(time);
    }

    static boolean[][] bfs(int[][] graph){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0));
        boolean[][] isAir = new boolean[graph.length][graph[0].length];
        isAir[0][0] = true;

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        while(!q.isEmpty()){
            Node now = q.poll();
            for(int i=0;i<4;i++){
                int newY = now.y + dy[i];
                int newX = now.x + dx[i];

                if(newY < 0 || newY >= graph.length || newX < 0 || newX >= graph[0].length) continue;
                if(isAir[newY][newX] || graph[newY][newX] != 0) continue;

                q.add(new Node(newY, newX));
                isAir[newY][newX] = true;
            }
        }

        return isAir;
    }

    static int melt(int[][] graph, boolean[][] isAir){
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        int meltCnt = 0;
        for(int i=0;i<graph.length;i++){
            for(int j=0;j<graph[0].length;j++){
                if(graph[i][j] != 1) continue;
                int count = 0;
                for(int k=0;k<4;k++){
                    int newY = i + dy[k];
                    int newX = j + dx[k];

                    if(newY < 0 || newY >= graph.length || newX < 0 || newX >= graph[0].length) continue;
                    if(isAir[newY][newX]) count++;
                    if(count >= 2) {
                        meltCnt++;
                        graph[i][j] = 0;
                        break;
                    }
                }
            }
        }

        return meltCnt;
    }

    static class Node{
        int y;
        int x;

        Node(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
}