[Algorithm] 백준 2636 치즈 - C++ ,BFS

2636번: 치즈

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

int c, r;
int cheese[101][101];
bool visit[101][101];
int totalCheese = 0;

int moveC[] = { 0, 0, 1, -1 };
int moveR[] = { 1, -1, 0, 0 };

bool IsOut(int row, int col){
    if(row > r || row < 0 || col < 0 || col > c)
        return true;
    return false;
}

bool TimeCount(int& cheeseCount){
    bool melted = false;
    int meltedCount = 0;
    queue<pair<int, int>> q;
    q.push({0, 0});

    while (!q.empty()){
        int curR = q.front().first;
        int curC = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nextR = moveR[i] + curR;
            int nextC = moveC[i] + curC;

            if(IsOut(nextR, nextC)) continue;
            if(visit[nextR][nextC]) continue;

            if(cheese[nextR][nextC] == 0){
                q.push({nextR, nextC});
            }
            else{
                meltedCount++;
                melted = true;
                cheese[nextR][nextC] = 0;
            }
            visit[nextR][nextC] = true;
        }
    }
    
    if(melted)
        cheeseCount = meltedCount;
    return melted;
}

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

    // input;
    cin >> r >> c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> cheese[i][j];
            if(cheese[i][j] == 1)
                totalCheese++;
        }
    }

    // solve
    int meltCount = 0;
    int cheeseCount = 0;
    while (true){
        memset(visit, false, sizeof(visit));
        if(TimeCount(cheeseCount) == false)
            break;
        meltCount++;
    }

    cout << meltCount << '\n';
    cout << cheeseCount << '\n';
    
}

---

 감 잡기가 어려웠던 문제다... 알고리즘 다시 열심히 해야겠다.

 일단 BFS를 돌리면서 몇번 치즈가 녹는지를 보면 되는데 문제는 '겉면의 치즈만 녹는' 문제입니다. 이걸 어떻게 하지? 각 치즈 정점에서 돌려야 하나? 생각을 했는데 좌측 위에서 시작하면 안쪽 치즈들은 영향 없이 탐색할 수 있다는 아이디어가 있었습니다. 이 아이디어를 통해서 탐색을 돌리고 마지막에 녹은 기록이 없다면 출력을 해주면 됩니다.