[백준] 2636.치즈

[문제]

www.acmicpc.net/problem/2636

2636번: 치즈

 

[풀이]

 

입력으로 사각형 판의 가로,세로 길이가 주어지고 사각형의 상태가 주어진다.

0은 비어있는 부분이고 1은 치즈가 존재하는 곳이다.

이 때 , 치즈가 공기와 접촉된 칸은 1시간 뒤에 녹아서 없어진다.

또한 치즈에 구멍이 있을 수 있는데 구멍에는 공기가 존재하지 않는다.

 

처음에 치즈에서 구멍을 먼저 찾아야겠다고 생각했다.

구멍을 찾는 방법으로는 사각형에서 치즈 밖의 부분은 0으로 모두 연결되어 있다.

따라서 BFS를 사용해 공기 부분을 찾았다.visited 배열을 사용해 방문한 곳에 대해 체크하였다.

map에서 값이 0인데 visited 배열에서도 방문하지 않아 0인 좌표는 치즈의 구멍이 된다.

치즈의 구멍 부분을 -1로 바꿨다.

solve 함수에서 좌표 값이 1인 부분 주변에 0이 존재하는  경우 치즈가 공기를 만나서 녹게 되는 부분이므로 map의 값을 -1로 바꿔주었다. 

 

이런식으로 1이 없을 때까지 반복하여 치즈가 모두 녹는데 시간을 구할 수 있다.

 

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <queue>
#include <vector>

#define MAX 101

using namespace std;

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

struct pos{
    int x,y;
};
int cnt=0;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

bool BFS()
{
    int visited[MAX][MAX]={0,};
    
    queue<pos> q;
    visited[0][0]=1;
    q.push({0,0});
    
    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 || visited[nx][ny] == 1 || map[nx][ny]==1) continue;
            q.push({nx,ny});
            visited[nx][ny] = 1;
            
        }
    }
    int num=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==0 && visited[i][j]==0)
                map[i][j]=-1;
            else if (map[i][j]==1)  num++;
        }
    }
    
    if(num==0)  return true;
    else return false;
}

void solve()
{
    cnt =0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==1){
                for(int k=0;k<4;k++)
                {
                    int nx= i+dx[k];
                    int ny= j+dy[k];
                    if(map[nx][ny] == 0){
                        cnt++;
                        map[i][j]=-1;
                        break;
                    }
                }
            }
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(map[i][j]==-1)   map[i][j]=0;
        }
    }
}
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 step =0;
    
    while(1){
        if(BFS())   break;
        solve();
        step++;
    }
    
    cout << step <<"\n" << cnt;
    
    return 0;
}