백준 2638번 치즈 [JAVA]

문제

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

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

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

 

 

 

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

 

 

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

 

예제

 

 

코드

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_BJ_2638_치즈 {
    static int N,M;
    static int [][] map, cheese;
    static boolean [][] visited;
    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;
        
        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        int time=0;
        while(true) {
            visited = new boolean[N][M];
            cheese = new int[N][M];
            
            dfs();
            if(cheeseMelt()) break;
            time++;
        }
        System.out.println(time);
    }
    
    public static void dfs() {
        Queue<int[]> queue = new LinkedList<int[]>();
        
        queue.offer(new int[] {0,0});
        visited[0][0]=true;
        
        while(!queue.isEmpty()) {
            int[] temp = queue.poll();
            
            for(int i=0;i<4;i++) {
                int nx = temp[0]+dx[i];
                int ny = temp[1]+dy[i];
                
                if(range(nx,ny) && !visited[nx][ny] ) {
                    if(map[nx][ny]==0) {
                        queue.offer(new int[] {nx,ny});
                        visited[nx][ny] = true;
                    }
                    else {
                        cheese[nx][ny]++;
                    }
                }
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<N && y<M;
    }
    
    public static boolean cheeseMelt() {
        
        int count=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(cheese[i][j]>1) {
                    map[i][j]=0;
                }
                else count++;
            }
        }
        
        if(count==N*M) return true;
        else return false;
    }
}

 

 

풀이방법

치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제였습니다. 이 문제에서 체크해야 할 부분이 치즈 격자의 4변 중에서 적어도 2변 이상이 공기와 접촉했을 경우 한시간 뒤 치즈가 녹는다는 점과, 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는다는 점입니다. 치즈가 상 하 좌 우 중 접촉하고 있는 변의 수를 세기 위해 cheese 배열을 만들어 탐색할 곳이 치즈라면 그 곳의 수를 늘려주는 방식으로 구현했습니다. 탐색을 끝낸 후, 2변 이상 공기와 접촉한 치즈는 녹아 없어지므로 0으로 바꿔주고 치즈가 몇 개 남아있는지 확인해 주었습니다. 격자에 치즈가 하나도 존재하지 않을 경우 while문을 종료하고 걸린 시간을 출력해주었습니다.