문제 : 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++];
}
}
'PS > BOJ' 카테고리의 다른 글
백준 20159 자바 - 동작 그만. 밑장 빼기냐? (BOJ 20159 JAVA) (1) | 2021.12.20 |
---|---|
백준 2806 자바 - DNA 발견 (BOJ 2806 JAVA) (0) | 2021.12.19 |
백준 1132 자바 - 합 (BOJ 1132 JAVA) (0) | 2021.12.18 |
백준 3011 자바 - 이름 지어주기 (BOJ 3011 JAVA) (0) | 2021.12.17 |
백준 12834 자바 - 주간 미팅 (BOJ 12834 JAVA) (0) | 2021.12.16 |
댓글