BOJ 2638 - 치즈

BOJ 2638 - 치즈

[분류 - BFS]

 

[풀이1]
  빈 공간이 보장되는 (0, 0)부터 계속 BFS를 돌면서 4방향에 대해 2방향 이상에 공기에 노출되는 경우에 대해서 삭제한다. 그러다가 모두 지워지는 시점을 출력한다.

[풀이2]
  빈 공간 (0, 0)부터 시작해서 공기가 될 부분, 즉 치즈가 사라질 부분을 또다른 큐에 넣도록 한다. 그러면 그 위치부터 공기가 시작되는 부분이기 때문에 [풀이1]에서 사용한 (0, 0)에서 다시 돌릴 필요가 없어지는 것이다.
  두 개의 큐를 사용하여 공기인 부분은 진행하고 치즈인데 2방향 이상이 공기에 맞닿은 부분이 있다면 다른 큐에 넣어두는 것이다.
  이 방식은 따로 명명할 방법이 없어 나는 토글 큐(toggle queue)라고 부르긴 한다.

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX_N = 100;
int main() {
    int N, M, i, j, b[MAX_N][MAX_N], vi[MAX_N][MAX_N] = {}, dy[] = { 0,0,1,-1 }, dx[] = { 1,-1,0,0 }, _time = -1, f = 0, t = 0;
    queue<pair<int, int>> q[2];
    scanf("%d%d", &N, &M);
    for (i = 0; i < N; i++) for (j = 0; j < M; j++) {
        scanf("%d", &b[i][j]);
        f |= b[i][j];
    }
    vi[0][0] = -1e9;
    q[t].push({ 0, 0 });
    while (!q[t].empty()) {
        while (!q[t].empty()) {
            auto u = q[t].front(); q[t].pop();
            for (i = 0; i < 4; i++) {
                int ty = u.first + dy[i], tx = u.second + dx[i];
                if (0 <= ty && ty < N && 0 <= tx && tx < M) {
                    vi[ty][tx]++;
                    if (vi[ty][tx] < 0) continue;
                    if (b[ty][tx] && vi[ty][tx] >= 2) {
                        vi[ty][tx] = -1e9;
                        q[!t].push({ ty, tx });
                    }
                    else if (!b[ty][tx]) {
                        vi[ty][tx] = -1e9;
                        q[t].push({ ty, tx });
                    }
                }
            }
        }
        _time++;
        t = !t;
    }
    printf("%d", _time);
    return 0;
}