[백준]치즈1

https://www.acmicpc.net/problem/2638

2638번: 치즈

종종 외곽을 처리해야 했던 유형에서 볼 수 있던 문제다..

처음에는 dfs로 조건을 걸어서 외곽을 저장하고 그걸로 녹이고 다시 외곽을 저장하는 식으로 생각을 했었는데

까다로울 것 같았다...

이 문제의 핵심은 외곽만을 없앤다 즉, 내부 공기까지 탐색을 하지 않는다 가 핵심이다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
int N, M;
int map[100][100];
bool isV[100][100];
queue<pair<int, int> >q; 
int ans = 0;
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
 
void bfs() {
    memset(isV, false, sizeof(isV));
    isV[0][0] = true;
    q.push(make_pair(0, 0));
 
    while (!q.empty()) {
        int r = q.front().first, c = q.front().second; q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= N || nc >= M || isV[nr][nc] == true) continue;
            if (map[nr][nc] >= 1) {
                map[nr][nc] += 1;
                continue; //치즈이면 하나 늘려줌.
            } //공기들만 탐색. (외부공기만) 내부까지 들어가지 않는다
            q.push(make_pair(nr, nc));
            isV[nr][nc] = true;
        }
    }
}
 
bool melt() {
    bool flag = false;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] >= 3) { //2변이상 닿음
                map[i][j] = 0; //녹이기
                flag = true;
            }
            else if (map[i][j] == 2) map[i][j] = 1; //1변만 닿음
        }
    }
    return flag;
}
 
int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
    
    while (1) {
        bfs();  //공기를 bfs로 탐색(외곽들만 탐색하기위해서!!)
        if (melt()==true) ans++; //녹으면 세서 진행.
        else break;
    }
 
    printf("%d\n", ans);
    return 0;
}