[백준 2636] 치즈

 

BFS로 치즈의 외곽을 구하고 반복된 시뮬레이션으로 정답을 도출했다.

 

1. 주어진 n, m을 n+2, m+2 하여 배열을 만든다. 치즈 외곽 탐색을 위해 편의상 바깥쪽 배열을 한칸씩 여유를 두었다.

2. 배열 탐색을 줄이기 위해 치즈의 개수를 세어 변수에 담는다.

3. 치즈가 녹기 전의 배열을 저장한다.

4. 외곽 치즈를 체크한다. (0, 0)은 무조건 치즈가 없으므로 BFS를 통해 치즈가 없는 부분을 모두 체크한다.

   (배열 값을 -1로 만들었다.)

5. 치즈 배열 인덱스에서 상하좌우 중 한개라도 -1이면 외곽의 치즈이므로 임의의 큐에 담는다.

6. 큐에 담은 좌표를 모두 0으로 바꾼다.

7. -1로 만든 외곽치즈를 다시 0으로 바꾼다.

 

public class Main {
    
    static int n;
    static int m;
    static int a[][];
    static int cheeze;
    static int prev[][];
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int cnt = 0;
    
    public static void main(String[] args) throws Exception {
        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());
        a = new int[n+2][m+2];
        prev = new int[n+2][m+2];
        
        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
                if(a[i][j] == 1) cheeze++;
            }
        }
        
        dfs();
    }
    
    public static void dfs() {
        if(cheeze == 0) {
            int k = 0;
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                    if(prev[i][j] == 1)
                        k++;
            
            System.out.println(cnt);
            System.out.println(k);
            return;
        }
        
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                prev[i][j] = a[i][j];
        
        checkOutside();
        
        Queue<Pair> q = new LinkedList<Pair>();
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(a[i][j] == 1)
                    if(a[i-1][j] == -1 || a[i+1][j] == -1 || a[i][j-1] == -1 || a[i][j+1] == -1) {
                        q.offer(new Pair(i, j));
                        cheeze--;
                    }
        
        while(!q.isEmpty()) {
            Pair p = q.poll();
            a[p.x][p.y] = -1;
        }
        
        for(int i=0; i<=n+1; i++)
            for(int j=0; j<=m+1; j++)
                if(a[i][j] == -1)
                    a[i][j] = 0;
        
        cnt++;
        dfs();
    }
    
    public static void checkOutside() {
        Queue<Pair> q = new LinkedList<Pair>();
        q.offer(new Pair(0, 0));
        a[0][0] = -1;
        
        while(!q.isEmpty()) {
            Pair p = q.poll();
            for(int i=0; i<4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if(0 <= nx && nx <= n+1 && 0 <= ny && ny <= m+1) {
                    if(a[nx][ny] == 0) {
                        a[nx][ny] = -1;
                        q.offer(new Pair(nx, ny));
                    }
                }
            }
        }
    }
    
    static class Pair {
        int x;
        int y;
        
        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}