[C++] 백준 2638 치즈

#include <iostream>
#include <queue>
 
using namespace std;
 
int n,m;
int arr[101][101];
bool air[101][101];
int time = 0;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0}; 
 
void input() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> arr[i][j];
        }
    }
}
 
bool checkDis(int x, int y) {
    int zero = 0;
    
    for(int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!air[nx][ny]) {
            zero++;
        }
    }
    
    if(zero > 2) { return true; }
    else { return false; } 
}
 
void checkMelting() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(arr[i][j] == 1 && !checkDis(i,j)) {
                arr[i][j] = 0;
            }
        }
    }
}
 
bool allCheck() {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(arr[i][j] == 1) {
                return false;
            }
        }
    }
    
    return true;
}
 
 
void checkAir() {
    queue<pair<int,int> > q;
    q.push({1,1});
    air[1][1] = true;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        air[x][y] = true;
        q.pop();
        
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m || air[nx][ny] || arr[nx][ny] == 1) { continue; }                        
            q.push({nx,ny});
            air[nx][ny] = true;
        }
    }
}
 
void solve() {
    while(1) {
        time++;
        
        checkAir(); 
        checkMelting();
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                air[i][j] = false;
            }
        }
        
        if(allCheck()) {
            cout << time;
            break;
        }
    }
    
}
 
int main() {
    input();
    solve();
    
}

 

 

단순 구현인줄 알고 접근했다가 뒤통수 맞은 문제

 

bfs 생각을 했다면 한시간은 더 빨리 풀었을텐데 bfs를 사용할 생각을 왜 못했을까..  

 

 

1. checkAir 메소드를 호출해 외부 공기와 내부 공기를 체크해야한다.

2. checkMelting 메소드를 호출해 외부 공기와 접촉하는 면이 2 이상일 경우 배열의 값을 0으로 바꿔준다.

3. 전체 배열을 순회하며 배열의 모든 값이 0 일 경우 시간을 출력하고 반복문을 종료한다.

 

이렇게 쓰고보니 어려울거 하나 없는 문제인데 골드 3이라고 괜히 쫄아서 꼬아 생각했다.