백준 2636번 치즈 [JAVA]

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어질 수도 있다.

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

 

 

 

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

 

 

 

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

 

 

 

예제

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_2636_치즈 {
    static int N,M, cheese;
    static int [][] map;
    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=1;
        while(true) {
            visited = new boolean[N][M];
            cheese=0;
            visited[0][0]=true;
            dfs(0,0);
            
            if(!check()) break;
            time++;
        }
        System.out.println(time+"\n"+cheese);
 
    }
    
    public static void dfs(int x, int y) {
        
        for(int i=0;i<4;i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(range(nx,ny) && !visited[nx][ny]) {
                visited[nx][ny]=true;
                
                if(map[nx][ny]==0) dfs(nx,ny);
                else {
                    map[nx][ny]=2; cheese++;
                }
            }
        }
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<N && y<M;
    }
    
    public static boolean check() {
        
        int count=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(map[i][j]==2) map[i][j]=0;
                else if(map[i][j]==1) count++;
            }
        }
        
        if(count==0) return false;
        else return true;
    }
 
}

 

 

풀이 방법

치즈가 모두 녹아서 없어지는 데 걸리는 시간과, 치즈가 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여 있는 칸의 개수를 구하는 문제였습니다.

 

저는 DFS를 이용해 문제를 풀었습니다. 여기서 주의할 점은 치즈의 구멍을 둘러싼 치즈는 녹지 않는다는 점입니다!

공기 중에 치즈를 놓으면 1초 뒤 그 치즈는 사라지게 됩니다. 저는 공기를 기준으로 상, 하, 좌, 우에 치즈가 있다면 그 치즈 자리를 2로 변경해주었습니다. 여기서 치즈 자리를 0이 아닌 2로 변경해주는 이유는 만약 바로 0으로 바꿔줬더라면 그 치즈 자리가 0이 되어 그 자리에서 상, 하, 좌, 우 에 있는 치즈 또한 공기 중에 놓여있어 사라지기 때문입니다. 그래서 dfs() 메서드를 통해 공기와 접촉한 치즈들의 자리를 2로 변경해준 뒤, check() 함수를 통해 위치의 값이 2인 곳을 0으로 바꿔주고 map에 치즈가 남아있는지 확인해주었습니다. 만약 치즈가 남아있지 않다면 반복문을 종료해 치즈가 모두 녹아서 없어지는 데 걸리는 시간과, 모두 녹기 한 시간 전에 남아있는 치즈 조각의 수를 출력해주었습니다.