[백준 2638] 치즈

 

치즈를 한턴의 bfs를 돌때 녹이지 않는게 중요하다.

bfs 돌때 녹여줘야하는 곳에 대한 정보를 저장해둔 후 bfs가 끝나고 녹여줘야한다.

 

치즈가 모두 없어질때까지 해야하므로

치즈 유무를 파악하면서 bfs를 계속 돌리면 된다

 

#include <iostream>
#include <bitset>
#include <queue>
#include <vector>

#define SIZE 101

using namespace std;

int N, M;
bitset<SIZE> map[SIZE];

int dy[4] = {-1, 0, 0, 1};
int dx[4] = {0, -1, 1, 0};

int count_cheese()
{
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        cnt += map[i].count();
    }
    return cnt;
}

void solve()
{
    queue<pair<int, int>> q;
    int cheese_touch[SIZE][SIZE] ={0,};

    bitset<SIZE> visited[SIZE];
    q.push(make_pair(0, 0));
    visited[0][0] = 1;

    int cury, curx, newy, newx;
    while (!q.empty())
    {
        cury = q.front().first;
        curx = q.front().second;
        q.pop();

        for (int i = 0; i < 4;i++){
            newy = cury + dy[i];
            newx = curx + dx[i];

            if(newy < 0 || newx < 0 || newy >= N || newx >= M) continue;

            // 아직 방문 안했고 0인 곳이면 방문
            if(!visited[newy][newx] && map[newy][newx]==0){
                visited[newy][newx] = 1;
                q.push(make_pair(newy, newx));
            }
            // 치즈면 접촉횟수 + 1
            else if(map[newy][newx]==1){
                cheese_touch[newy][newx]++;
            }
        }
    }

    // cheese 지우기
    for (int i = 0; i < N;i++){
        for (int k = 0; k < M;k++){
            // 2번 이상 접촉된 곳이면 치즈 삭제
            if(cheese_touch[i][k]>=2){
                map[i][k] = 0;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;

    int x;
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < M; k++)
        {
            cin >> x;
            map[i][k] = x;
        }
    }

    int ans = 0;
    while (count_cheese())
    {
        solve();
        ans++;
    }

    cout << ans;

    return 0;
}