[백준][2638번] 치즈 [cpp, c++]

백준 2638 치즈 

• BFS를 이용한 문제이다.
• https://www.acmicpc.net/problem/2638

2638번: 치즈

 

• 풀이 방법

  1) 외부 공기와 내부 공기를 분리한다. (BFS 사용) - 함수명 outsideBFS()
   - 문제 조건에 맨 가장자리는 치즈가 놓이지 않는다고 했으니, 0,0을 큐에 넣어서 외부 공기를 체크한다.
   - 여기에 체크되지 않은 공간은 외부 공기가 아니다.
  2) BFS를 통해 녹을 수 있는 치즈를 체크한다. - 함수명 : BFS => melt라는 배열에 check
   - 외부 공기와 2면 이상 인접하면 그 치즈는 녹는 치즈이다.
  3) 녹는 배열을 체크해서 치즈를 녹인다.
  4) 치즈가 다 녹을 때 까지 1~3을 반복한다.

 

 

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;

int dx[5] ={1,0,-1,0};
int dy[5] ={0,1,0,-1};
int N,M;
int paper[101][101];
int outAir[101][101];
int melt[101][101];
struct point{
    int x,y;
};
queue<point> q;
queue<point> q1;
void inputData(){
    cin>>N>>M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>paper[i][j];
        }
    }
}


void BFS(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(paper[i][j]==1) q1.push({i,j});
        }
    }
    while(!q1.empty()){
        int x = q1.front().x, y = q1.front().y;
        q1.pop();
        int cnt = 0;
        for(int i=0;i<4;i++){
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
            if(outAir[nx][ny]==1) cnt ++;
        }
        if(cnt>=2) melt[x][y] = 1; //녹는 부분
        
    }
}


void outsideBFS(){
    q.push({0,0});
    while(!q.empty()){
        int x = q.front().x, y= q.front().y;
        q.pop();
        for(int i=0;i<4;i++){
            int nx = dx[i] + x;
            int ny = dy[i] + y;
            if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
            if(paper[nx][ny] || outAir[nx][ny]) continue;
            outAir[nx][ny] += 1 ;
            q.push({nx,ny});
        }
    }
}

void meltCheeze(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(melt[i][j]==1) paper[i][j] = 0;
        }
    }
}

int checkMelt(){
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(paper[i][j]==1) return 0;
        }
    }
    return 1;
}


void sol(){
    int ans = 0 ;
    inputData();
    while(1){
        if(checkMelt()==1) break;
        outsideBFS();
        BFS();
        meltCheeze();
        ans++;
        memset(outAir, 0, sizeof(outAir));
        memset(melt, 0, sizeof(melt));
    }
    cout<<ans<<"\n";
}


int main(void){
    sol();
    return 0;
}