[BOJ] 2638. 치즈

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

2638번: 치즈

앞에서 풀었던 2636번 치즈 (풀이 링크)문제와 비슷한 문제이다.

다른 점은 4 변 중 2 변 이상이 공기에 접촉해야 치즈가 놓는다.

답도 시간만 출력하면 된다.

 

 

앞의 문제와 마찬가지로 테두리에는 치즈가 없으므로

(0,0)을 먼저 큐에 넣어 바깥 영역을 먼저 bfs로 구하고

치즈가 두번 이상 바깥 영역(공기 부분)과 접촉해있다면 치즈가 녹는다(0이 된다).

 

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
int r, c;
int board[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
 
//치즈수를 카운트
int countCheese() {
    int cnt = 0;
    for (int i = 1; i < r - 1; i++) {
        for (int j = 1; j < c - 1; j++) {
            if (board[i][j] == 1) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
 
 
void solve() {
 
    //bfs로 바깥 영역을 체크
    queue<pair<int, int>> q;
    memset(check, false, sizeof(check));
    int x = 0;
    int y = 0;
 
    q.push(make_pair(x,y));
    check[x][y] = true;
 
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if (check[nx][ny]) continue;
            if (board[nx][ny] == 1) continue;
 
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;;
        }
    }
 
 
 
    for (int i = 1; i < r-1; i++) {
        for (int j = 1; j < c-1; j++) {
            if (board[i][j] == 0) continue;
 
            
            int cnt = 0;
            //네방향을 검사
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (check[nx][ny]) {
                    //공기에 접촉하는 횟수
                    cnt++;
                }
            }
 
 
            //두 변 이상 공기에 접촉하면 녹는다.
            if (cnt >= 2) {
                board[i][j] = 0;
            }
        }
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
 
    int time = 0;
    while (true) {
        int tmp = countCheese();
 
        //치즈가 모두 녹으면 break
        if (tmp == 0) {
            break;
        }
    
        solve();
        time++;
    }
 
    cout << time << '\n';
 
 
    return 0;
}