[C++] 치즈 (백준 2638번)

https://www.acmicpc.net/problem/2638

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m;
vector<vector<bool>> g;

bool bfs() {
    vector<vector<bool>> vst(n, vector<bool>(m, false));
    vector<vector<bool>> out(n, vector<bool>(m, false));
    bool finish = true;

    queue<pair<int, int>> q;
    q.emplace(0, 0);
    vst[0][0] = true;
    while (!q.empty()) {
        int curi = q.front().first;
        int curj = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nxti = curi + dx[i];
            int nxtj = curj + dy[i];
            if (nxti >= 0 && nxti < n && nxtj >= 0 && nxtj < m && !vst[nxti][nxtj]) {
                vst[nxti][nxtj] = true;
                if (g[nxti][nxtj]) {
                    finish = false;
                    int cnt = 0;
                    for (int j = 0; j < 4; j++) {
                        if (!g[nxti + dx[j]][nxtj + dy[j]]) cnt++;
                    }
                    if (cnt >= 2) out[nxti][nxtj] = true;
                } else {
                    q.emplace(nxti, nxtj);
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (out[i][j]) {
                g[i][j] = false;
            }
        }
    }

    return finish;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    g = vector<vector<bool>>(n, vector<bool>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            g[i][j] = x;
        }
    }

    int time = 0;
    bool isFinished = false;
    while (!isFinished) {
        isFinished = bfs();
        time++;
    }
    
    cout << time - 1 << '\n';
}

원래 한번씩 쭉 이중반복문으로 탐색하면서 1인 곳을 발견할 때마다 상하좌우로 4번을 bfs하면서 벽에 닿는 곳이 2개 이상인지 체크하려고 했는데(...) 누가봐도 시간초과니까... 어떻게 풀어야 하지 고민하다가 질문 게시판을 스을쩍 참고했다. 그래서 벽에서 bfs를 시작해서 외각치즈를 먼저 구한다는 아이디어 겟!! 그래서 외각치즈 중 상하좌우가 0인게 2개 이상이면 체크해뒀다가 0으로 만드려고.. 했는데... (오답)

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n, m;
vector<vector<bool>> g;

bool bfs() {
    vector<vector<bool>> vst(n, vector<bool>(m, false));
    vector<vector<int>> out(n, vector<int>(m, 0));
    bool finish = true;

    queue<pair<int, int>> q;
    q.emplace(0, 0);
    vst[0][0] = true;
    while (!q.empty()) {
        int curi = q.front().first;
        int curj = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nxti = curi + dx[i];
            int nxtj = curj + dy[i];
            if (nxti >= 0 && nxti < n && nxtj >= 0 && nxtj < m && !vst[nxti][nxtj]) {
                if (g[nxti][nxtj]) {
                    finish = false;
                    out[nxti][nxtj]++;
                    if (out[nxti][nxtj] >= 2) vst[nxti][nxtj] = true;
                } else {
                    q.emplace(nxti, nxtj);
                    vst[nxti][nxtj] = true;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (out[i][j] >= 2) {
                g[i][j] = false;
            }
        }
    }

    return finish;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    g = vector<vector<bool>>(n, vector<bool>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            g[i][j] = x;
        }
    }

    int time = 0;
    bool isFinished = false;
    while (!isFinished) {
        isFinished = bfs();
        time++;
    }
    
    cout << time - 1 << '\n';
}

다시 한 번 질문 게시판을 스윽 참고해주고 ㅋㅋㅋ 외각치즈의 상하좌우를 체크할 때 그냥 0인게 2개 이상인지 확인하는 게 아니라! 외부 공기가 2개 이상인지를 확인해야 하는 것이었다! 그 로직을 추가했더니 맞았다. (정답)