[백준] 치즈 2636 bfs

문제 :

www.acmicpc.net/problem/2636

2636번: 치즈

 

분석 :

이 문제는 생각하기 복잡했지만 코드를 보니 단숨에 이해가 가는 듯 한 문제였다.

치즈의 겉면만 시간에 따라 어떻게 공기로 바꿀까 문제 그대로의 흐름을 따라 문제를 풀려 했지만 그렇게 되면은 안쪽의 공기와 바깥쪽의 공기가 구분이 되지 않아 순서가 엉망이 될 수도 있을 것 같았다. 

같이 스터디 하는 언니의 코드 설명으로 치즈 입장에서가 아닌 공기 입장에서 다음 공기가 될 것인지 아닌지 판단하면 안쪽의 공기를 생각하지 않아도 된다는 점이 신기했다. 녹는 순서는 공기에 닿는 순서이므로 먼저 안쪽 공기를 만날일이 없기 때문이다. 

enum을 사용해서 더욱 간결하게 작성했더라 최고다 최고 

 

find_air 함수가 false가 될 조건은 남아있는 치즈가 있는지 없느지 melt_bfs로 검사하여 판별한다. 하나라도 1 cheese가 남아있을 경우 while문을 돌며 cheese를 녹인다. 

 

c++ 코드 :

 

//
//  2636_cheese.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/01.
//

#include <stdio.h>
#include <iostream>
#include <queue>
#include <cstring>


using namespace std;
int arr[101][101];
int visit[101][101];
int cheese_cnt = 0;
int ans = 1;
int M, N;

int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

enum { CHEESE = 1, PREAIR, AIR};

bool melt_bfs(){
    bool cleared = true;
    for(int i = 0; i < M; i++){
        for(int j = 0; j < N; j++){
            if(arr[i][j] == PREAIR){
                arr[i][j] = AIR; // 공기로 바꿔줌
            }
        }
    }
    
    for(int i = 0; i < M; i++){
        for(int j = 0; j < N; j++){
            if(arr[i][j] == CHEESE){//치즈가 조금이라도 남았다면 false
                cleared = false;
            }
        }
    }
    return cleared;

    
}

bool find_air(){
    queue<pair<int, int>> q;
    q.push(make_pair(0,0));
    memset(visit, false, sizeof(visit));
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        
        arr[y][x] = AIR;
        q.pop();
        for(int i = 0; i < 4; i ++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= M || nx >= N || visit[ny][nx])
                continue;
            if(arr[ny][nx] == CHEESE){ // 근처 치즈를발견하면 preair로 넣어준다 ..!
                arr[ny][nx] = PREAIR;
                cheese_cnt++;
            }else if (arr[ny][nx] == 0 || arr[ny][nx] == AIR){
                q.push(make_pair(ny, nx)); // 공기에 대해 q에 넣어준다.
                visit[ny][nx] = true;
            }
            
        }
    }
    return melt_bfs();
}

int main(){
    cin >> M >> N;
    for(int i = 0; i < M; i++){
        int s;
        for(int j = 0; j < N; j++){
            cin >> s;
            arr[i][j] = s;
        }
    }
    
//    for(int i = 0 ; i < M; i++){ //input 확인용
//        for(int j = 0; j < N; j++){
//            cout << arr[i][j] << " ";
//        }
//        cout << endl;
//    }
    
    while(1){
        cheese_cnt = 0;
        if(find_air())
            break;
        ans++;
    }
    
    cout << ans << '\n';
    cout << cheese_cnt << '\n';
    
    melt_bfs();
    
    
    return 0;
}