[백준] 2638번. 치즈

[문제]

 

www.acmicpc.net/problem/2638

2638번: 치즈

 

[풀이]

 

모눈종이 위에 치즈가 존재하고 , 치즈가 공기와 접촉하는 변이 2개 이상일 경우 한시간 뒤에 녹게된다.

(치즈 내부에 있는 치즈 공간은 공기와 접촉하지 않는 것으로 가정한다. )

이 때 치즈가 모두 녹는데 걸리는 시간을 구하는 문제이다.

 

BFS를 사용해 외부 공간을 queue에 저장하였다.

queue에서 하나씩 pop 할 때마다 해당 좌표의 상하좌우 중에서 치즈가 존재하는지 확인한다.

치즈가 존재한다면 , 치즈가 존재하는 좌표의 visited 배열 값을 +1 해준다.

 

위와 같이 반복하여 while문을 나왔을 때, visited 배열의 값이 2 이상인 경우 접촉하는 변이 2개 이상인 경우이므로 

해당 좌표 map 배열의 값을 0으로 update 해준다. 

 

 

 

[코드]

 

시간 : 8ms

 

#include <iostream>
#include <queue>
#define MAX 101

using namespace std;

struct pos{
    int x,y;
};

int map[MAX][MAX]={0,};
int N,M;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

bool BFS()
{
    bool flag= false;
    
    int visited[MAX][MAX]={0,};
    
    queue <pos> q;
    q.push({0,0});
    visited[0][0]=-1;
    
    while(!q.empty()){
        
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx<0 || ny < 0 || nx >= N || ny >= M)    continue;
            if(map[nx][ny] == 1){
                visited[nx][ny]++;
                continue;
            }
            if(visited[nx][ny]!=0)  continue;
            
            q.push({nx,ny});
            visited[nx][ny] = -1;
            
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(visited[i][j] >= 2){
                map[i][j] = 0;
                flag = true;
            }
        }
    }
    
    return flag;
}

int main(void)
{
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)    cin >> map[i][j];
    }
    
    int cnt =0;
    
    while(1){
        if(BFS()==false)    break;
        cnt++;
    }
    
    cout << cnt;
    return 0;
    
}