[Jungol] 정올 1840 치즈

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=30

 Input 

13 12

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 1 0 0 0

0 1 1 1 0 0 0 1 1 0 0 0

0 1 1 1 1 1 1 0 0 0 0 0

0 1 1 1 1 1 0 1 1 0 0 0

0 1 1 1 1 0 0 1 1 0 0 0

0 0 1 1 0 0 0 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 1 1 1 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

 

 Output 

3

5

 

 

① 가장자리는 치즈가 없는 곳입니다.

    따라서 임의의 지점 (0, 0)에서 BFS 탐색하며 공기와 접촉된 치즈를 찾습니다.

    - 공기에 해당되는 지점을 중복없이 que[]에 보관합니다.

    - [특정 시간] 공기와 접촉되어 없어지는 치즈 정보를 cheese[]에 저장합니다.

 

② 공기와 접촉되어 녹는 치즈가 전부 없어질 때까지 반복

③ BFS 탐색을 반복해야 하기 때문에 초기화에 유의합니다.

④ 첫번째 답인 전체 치즈가 녹는 시간은 모든 치즈가 녹을 때까지 반복된 시간이며,

     두번째 답인 전체 녹기 직전 남아있는 치즈개수는 마지막으로 녹일 것이 존재했던 치즈의 개수입니다.

---

#include <stdio.h>
 
const int MAX_RC = 100 + 5;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
int N, M, ans2;
int map[MAX_RC][MAX_RC], visited[MAX_RC][MAX_RC];
struct Node {
    int x, y;
}que[MAX_RC * MAX_RC * 4], cheese[MAX_RC * MAX_RC];
int fr, re, cfr, cre;
 
void init() {
    fr = re = cfr = cre = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            visited[i][j] = 0;
        }
    }
}
 
int BFS() {
    // 초기화
    init();
    que[re++] = { 0, 0 };
    visited[0][0] = 1;
    // 공기와 접촉되어 녹는 치즈 개수
    int cheeseCnt = 0;
    while (fr < re) {
        Node cur = que[fr++];
 
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.x + dx[i];
            int nextY = cur.y + dy[i];
 
            if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
                continue;
            if (visited[nextX][nextY])
                continue;
 
            visited[nextX][nextY] = 1;
 
            // 공기와 접촉하는 치즈인 경우
            if (map[nextX][nextY]) {
                cheese[cre++] = { nextX, nextY };
                cheeseCnt++;
                // 치즈 표시만 하고 탐색 큐에는 넣지 않습니다.
                continue;
            }
            que[re++] = { nextX, nextY };
        }
    }
    return cheeseCnt;
}
 
void meltCheese() {
    while (cfr < cre) {
        Node cur = cheese[cfr++];
        map[cur.x][cur.y] = 0;
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
 
    int time = 0;
    while (1) {
        // 녹여지는 치즈 개수
        int targetCnt = BFS();
        if (targetCnt > 0) {
            time++;
            ans2 = targetCnt;
            meltCheese();
            continue;
        }
        
        printf("%d\n", time);
        printf("%d\n", ans2);
        return 0;
    }
    
}