백준 2636 치즈 (C++)

2636번: 치즈

bfs를 아용하는 문제이다. 문제를 보면 치즈의 겉면부터 한 겹씩 녹는 것을 알 수 있다. 즉 치즈가 아니라 공기를 기준으로 bfs를 해주어야 한다. 먼저 배열을 입력 받으면서 치즈 칸 갯수를 카운트 해준다. 반복문을 돌면서 0,0에서 bfs를 돌려준다. bfs를 돌면서 다음 좌표가 치즈일 경우 이를 카운트하고 0으로 바꿔준다. 그리고 방문 표시인 check[ny][nx] = true를 해줘야 하는데 재방문을 막아 첫 겉면만을 녹이기 위해 사용해 주었다. 모든 겉면을 녹인 후 치즈 칸 갯수에서 카운트한 값을 빼주는 데 만약 0이 된다면 이전의 값을 따로 저장해주었다. 반복문을 돌때마다 시간을 카운트해주고 치즈 칸 갯수가 0이 되면 종료를 하고 시간과 모두 녹기 1시간 전 치즈 칸 갯수를 출력해주었다. 처음에는 치즈를 기준으로 bfs를 생각하여 시간을 많이 잡아먹었다. 이러한 유형에 대해 잘 알아두자.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N, M, cheez = 0;
int A[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool check[100][100];
int result1 = 0, result2 = 0;

void bfs(int a, int b) {
    queue<pair<int, int>> q;
    int count = 0;

    q.push({ a, b });
    check[a][b] = true;

    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
            if (check[ny][nx]) continue;
            if (A[ny][nx]) {
                A[ny][nx] = 0;
                check[ny][nx] = true;
                count++;
                continue;
            }

            q.push({ ny,nx });
            check[ny][nx] = true;
        }
    }

    if (cheez - count == 0) result2 = cheez;
    cheez -= count;
}

void solution() {
    while (cheez) {
        memset(check, false, sizeof(check));

        bfs(0, 0);
        result1++;
    }

    cout << result1 << "\n";
    cout << result2 << "\n";
}

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

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];

            if (A[i][j]) {
                cheez++;
            }
        }
    }

    solution();

    return 0;
}