백준 2638 치즈 - 여러번 bfs를 돌려야하는 문제

문제 링크

www.acmicpc.net/problem/2638

2638번: 치즈

풀이 아이디어

문제를 풀기 위해 핵심적으로 파악해야 하는 여부가

'치즈가 외부 공기와 2군데 이상 닿아 있는지 여부를 확인하자' 이다.

치즈가 전부 녹아 없어질때까지 이 여부를 확인해보면서 진행 해야한다.

 

주의할 것이 내부 공기는 외부 공기가 아니므로,

단순히 치즈 주변이 0으로 둘러 쌓여 있는가를 가지고 판단하면 안된다.

 

확실한 외부 공기로부터 bfs를 통해 치즈가 외부 공기와 닿아있는지 여부를 확인해 보았다.

나는 0,0 외부공기부터 큐에 넣고, 확산 시키면서

치즈에 닿았을땐 치즈 값을 1 증가시키고,

안 닿았을땐 다시 큐에 넣어가며 bfs를 진행시켰다.

 

그후 외부 공기와 닿은 횟수가 2회 이상인 치즈들은 빼면서 다시 진행시키고,

이런 식으로 코드를 진행시켰다.

코드

#include <bits/stdc++.h>
using namespace std;
int n,m;
int cheeze[101][101];
bool visited[101][101];
int ans=0;
queue<pair<int,int>> q;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};


bool check(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(cheeze[i][j]) return false;
        }
    }
    return true;
}

void melt(){
    ans++;
    int tmp[n][m];
    for(int i=0; i<n;i++) {
        for (int j = 0; j < m; j++) {
            tmp[i][j] = cheeze[i][j];
            visited[i][j]=false;
        }
    }

    q.push({0,0});
    visited[0][0] = true;
    int x,y;
    while(!q.empty()){
        tie(x,y) = q.front();
        q.pop();
        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) continue;
            if(visited[nx][ny]) continue;
            if(cheeze[nx][ny]) cheeze[nx][ny]++;
            if(!cheeze[nx][ny]){
                visited[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }

    for(int i=0; i<n;i++){
        for(int j=0; j<m; j++){
            if(cheeze[i][j]-1 >=2){
                tmp[i][j]=0;
            }
            cheeze[i][j]= tmp[i][j];
        }
    }
}

int main(void){
    cin>>n>>m;
    for(int i=0; i<n;i++)
        for(int j=0; j<m; j++)
            cin>>cheeze[i][j];

    while(!check()){
        melt();
    }
    cout<<ans;
}