[백준/C++] 2638번 치즈

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

2638번: 치즈

얼핏보면 까다로운 문제처럼 보일 수 있지만, 이 문제의 키포인트는 치즈의 외부 공기와 내부 공기를 잘 구분하면 된다!

그렇게 할 수만 있다면 외부 공기와 2면 이상 닿은, 즉 곧 녹을 치즈를 구하는 건 어렵지 않다.

​

그렇다면 어떻게 외부 공기와 내부 공기를 구분할까?

가장자리에는 치즈가 올 수 없다고 하였으므로, (0,0)에서 부터 bfs를 시작한다.

0,0에서 bfs를 통해 갈 수 있는 모든 곳은 외부 공기로, 굳이 표현해주지 않아도 되지만 2로 표현해주었다.

그리고 1을 만나면 (=치즈를 만나면) 외부 공기와 닿은 면의 수를 저장해주기 위한 배열을 하나 선언해준뒤, 해당 인덱스의 값을 1 증가 시켰다. 1을 만났을 땐, 큐에 넣는다던지 이런 작업없이 위처럼 배열의 인덱스만 1 증가 해주고 다음 for문을 실행하였기 때문에, 내부 공기(1 안에 있는 0)에 접근할 수 없게 된다!

그리고 한 점에 대한 bfs가 끝날 때 마다 externAir 배열이 2보다 큰 곳이 있다면(=녹는 치즈가 있다면) 0으로 없애주었고 true를 리턴하였다.

boolean 타입의 함수를 사용한 이유는, 더이상 녹을 수 있는 치즈가 없을 때 까지 반복해주기 위함이다!

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <cstring>

using namespace std;

int map[101][101];
int visited[101][101];
int externAir[101][101];
queue<pair<int,int>> q;
int n,m,ans;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};


void bfs(int a, int b){
    q.push({a,b});
    map[a][b]=2;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if(visited[x][y]) continue;
        visited[x][y] = true;
        map[x][y]=2;
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if(map[nx][ny]==1) externAir[nx][ny]++;
                else if(!visited[nx][ny]){
                    q.push({nx,ny});
                }
            }
        }
    }
}
bool update(){
    bool flag = false;
    for(int i=0; i<n; i++) {
        for (int j = 0; j < m; j++) {
            if(externAir[i][j]>=2){
                map[i][j]=0;
                flag = true;
            }
        }
    }
    return flag;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    while(1) {
        memset(externAir,0,sizeof(externAir));
        memset(visited,0,sizeof(visited));
        bfs(0, 0);
        if (update()) {
            ans++;
        }
        else break;
    }
    cout << ans;
    return 0;
}