백준 2636 자바 - 치즈 (BOJ 2636 JAVA)

문제 : boj2636

 

 

1.

  우선 '치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.' 부분부터 생각해보자. 1로 막혀있는 0 부분은 공기로 치지 않는다는 의미로, 이 조건에 따라 단순히 '0'과 인접한 '1'만 찾아선 안된다.

 

  탐색에 익숙하지 않다면 아이디어를 떠올리기 힘들 수 있다. 이 문제의 경우 외부 공기에서부터 탐색을 시작하면 치즈로 둘러쌓인 내부는 보지 않을 수 있다. 그리고 이 문제는 친절하게 판의 가장자리에는 치즈가 놓여있지 않다고 한다. 그러니 단순하게 0,0 지점에서 시작하면 언제나 외부 공기에서 시작함을 보장할 수 있다. 따라서 모든 치즈가 사라질 때 까지, 0,0 부터 시작하는 bfs 혹은 dfs를 계속 반복하고, 그때마다 시간이 1씩 증가하면 녹는데 걸리는 시간을 알 수 있다.

 

2.

  그럼 '모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수'는 어떻게 구할 수 있을까? 간단하게 하자면 '1'을 수행하면서 0,0 부터 시작하는 탐색 전에 이전 치즈 모양에 대한 복사 배열을 두면 쉽게 할 수 있을 것 같다. 복사 배열을 tmp[][] 라 하면, 치즈가 사라질때까지 '1'을 진행하면 tmp에 있는게 1시간 전에 남은 치즈조각의 모양일테니 여기서 조각의 개수를 구하면 된다.

 

  하지만 이 경우 당연히 비효율적이기 때문에, 내 경우엔 해당 시간에 제거된 치즈는 '-시간'으로 배열에 기록해두었다. 예를들어 '예제 입력1'에 대해 모든 치즈가 사라진 후 배열의 모습은 다음과 같다. -1은 1시간 후에 제거된 치즈, -2는 2시간 후, -3은 3시간 후에 제거된 치즈이다.

 

  탐색이 종료된 후(제거된 치즈가 하나도 없다면 종료) 구해진 시간에 제거된 치즈만 남기면 다음과 같이 다 사라지기 전에 남아있던 치즈 조각의 모양이 된다.

그럼 각 지점들을 dfs 혹은 bfs로 탐색하며 조각의 수를 세면 답을 구할 수 있다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    boolean removed;
    boolean[][] v;

    private boolean hourProc(int r, int c, int[][] arr, int hour, int cr, int cc) {
        if (arr[cr][cc] == 1) {
            arr[cr][cc] = -hour;
            removed = true;
            return removed;
        }

        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (((dr^dc)&1)==0) continue;

                int nr = cr+dr;
                int nc = cc+dc;
                if (nr < 0 || nr >= r || nc < 0 || nc >= c || v[nr][nc]) continue;
                v[nr][nc] = true;
                hourProc(r, c, arr, hour, nr, nc);
            }
        }
        return removed;
    }

    private void removePiece(int r, int c, int[][] arr, int cr, int cc) {
        if (arr[cr][cc] == 1) {
            arr[cr][cc] = 0;
            return;
        }

        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                if (((dr^dc)&1)==0) continue;

                int nr = cr+dr;
                int nc = cc+dc;
                if (nr < 0 || nr >= r || nc < 0 || nc >= c || v[nr][nc]) continue;
                removePiece(r, c, arr, nr, nc);
            }
        }
    }

    private void solution() throws Exception {
        int r = nextInt();
        int c = nextInt();
        int[][] arr = new int[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                arr[i][j] = nextInt();
            }
        }

        int hour = 0;
        do {
            v = new boolean[r][c];
            removed = false;
        } while (hourProc(r, c, arr, ++hour, 0, 0));

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j] == -(hour-1))
                    arr[i][j] = 1;
                else
                    arr[i][j] = 0;
            }
        }

        int lastSplitCnt = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (arr[i][j]==1) {
                    lastSplitCnt++;
                    v = new boolean[r][c];
                    removePiece(r, c, arr, i, j);
                }
            }
        }
        System.out.println(hour-1);
        System.out.println(lastSplitCnt);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}