Baekjoon 2638번 치즈

문제

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

걸린 시간

00 : 24 : 06

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> paper(n, vector<int>(m));
    vector<pair<int, int>> cheese;
    for(int y = 0; y < n; y++)
        for(int x = 0; x < m; x++)
            cin >> paper[y][x];
    int dy[4] = {-1, 1, 0, 0};
    int dx[4] = {0, 0, -1, 1};
    int ans = 0;
    while(true){
        vector<vector<int>> visited(n, vector<int>(m, 0));
        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));
        visited[0][0] = 1;
        while(!q.empty()){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            for(int i = 0; i < 4; i++){
                int ny = y+dy[i];
                int nx = x+dx[i];
                if(0 <= ny && ny < n && 0 <= nx && nx < m && !visited[ny][nx] && paper[ny][nx] == 0){
                    visited[ny][nx] = 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
        for(int y = 0; y < n; y++){
            for(int x = 0; x < m; x++){
                if(paper[y][x] != 1) continue;
                int air = 0;
                for(int i = 0; i < 4; i++){
                    int ny = y+dy[i];
                    int nx = x+dx[i];
                    if(paper[ny][nx] == 0 && visited[ny][nx]) air++;
                }
                if(air >= 2) cheese.push_back(make_pair(y, x));
            }
        }
        if(cheese.size() == 0) break;
        for(int i = 0; i < cheese.size(); i++){
            int y = cheese[i].first;
            int x = cheese[i].second;
            paper[y][x] = 0;
        }
        cheese.clear();
        ans++;
    }
    cout << ans;
    return 0;
}

치즈 내부에 있는 공간과 접촉할 경우에는 녹지 않는다는 조건을 빠뜨리고 읽어 두번만에 ac를 받았다.