2638 치즈

2638 치즈

1. 가장자리는 무조건 공기라고 문제에서 주어졌으므로, 가장자리에서 시작해 공기부분을 초기화 시킨다.

2. 공기와 두칸이상 맞닿은 부분을 vector에 기록하고 공기로 바꾼다.

3. 남은 치즈의 개수를 센다.

4. 치즈가 다 사라진 시간을 출력한다.

#include <iostream>
#include <vector>
#define P pair<int,int>
using namespace std;
 
int n, m;
int map[100][100];
bool visited[100][100];
vector<P> v;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int getCount() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++){
            if (map[i][j] == 1) ans++;
        }
    }
    return ans;
}
 
void newAir(int x,int y) {
    map[x][y] = 2;
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if (ax >= 0 && ay >= 0 && ax < n&&ay < m && map[ax][ay]!=1 && !visited[ax][ay]) {
            newAir(ax, ay);
        }
    }
}
 
void contactAir(int x,int y) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if (map[ax][ay] == 2) cnt++;
    }
    if (cnt > 1)
        v.push_back(P(x, y));
}
 
void initVisited() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            visited[i][j] = false;
        }
    }
}
 
/*
0 : 치즈내부
1 : 치즈
2 : 공기
*/
int main() {
    scanf("%d%d", &n, &m);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    int cnt = 0;
    int time = 0;
    while ((cnt = getCount()) != 0) {
        time++;
        //공기부분 갱신
        newAir(0, 0);
        initVisited();
        //공기와 접촉한 치즈 제거
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                contactAir(i, j);
            }
        }
 
        for (int i = 0; i < v.size(); i++) {
            map[v[i].first][v[i].second] = 2;
        }
        v.clear();
 
    }
    printf("%d\n", time);
}