[KOI] 백준 2638 - 치즈

www.acmicpc.net/problem/2638

2638번: 치즈

 

KOI 중등부 치즈문제이다.

 

중등 치즈에서는 치즈 격자가 외부 공기와 두변 이상 접촉해야 녹는다고 하며 치즈를 모두 녹이는데 필요한 시간을 구해야 한다.

 

또한 모눈 종이에 가장자리에는 치즈가 놓이지 않는다는 조건이 있다.

 

이를 공기의 관점으로 접근하면 문제를 해결할 수 있다.

 

1. BFS로 공기를 흘려보낸다. 가장자리에는 치즈가 놓이지 않으므로 탐색 시작점은 (0, 0)이 적절할 것이다.

공간을 탐색하면서 치즈와 접촉할 때마다 해당 치즈의 공기 접촉 횟수를 기록한다.

 

2. 탐색이 완전히 끝난 후 2번 이상 공기와 접촉한 치즈는 녹는 치즈이므로 배열에 이를 반영한다.

이 과정을 치즈가 다 녹을 때까지 반복하면 된다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int cheese[100][100];
int meltdown[100][100];
int visit[100][100];
int mx[4] {0, 0, 1, -1};
int my[4] {1, -1, 0, 0};

int remain = 0;
int remain_past = 0;
int cnt = 0;

vector<vector<int>> airflow(int r, int c)
{
    memset(meltdown, 0, sizeof meltdown);
    memset(visit, 0, sizeof visit);
    vector<vector<int>> bounding;
    queue<vector<int>> dimention;
    dimention.push({0, 0});
    visit[0][0] = 1;
    
    while (!dimention.empty())
    {
        vector<int> curr = dimention.front();
        dimention.pop();
        
        for (int i = 0; i < 4; ++i)
        {
            int nx(mx[i] + curr[0]), ny(my[i] + curr[1]);
            if (nx < 0 || ny < 0 || nx >= r || ny >= c || visit[nx][ny])
                continue;

            if (cheese[nx][ny])
                ++meltdown[nx][ny];
            else
            {
                dimention.push({nx, ny});
                visit[nx][ny] = 1;
            }
        }
    }
    
    for (int j = 0; j < r; ++j)
        for (int k = 0; k < c; ++k)
            if (meltdown[j][k] >= 2)
                bounding.push_back({j, k});
    
    return bounding;
}

int main() 
{
    memset(cheese, -1, sizeof cheese);
    int r, c; cin >> r >> c;

    for (int i = 0; i < r; ++i)
        for (int j = 0; j < c; ++j)
        {
            cin >> cheese[i][j];
            if (cheese[i][j])
                ++remain;
        }

    remain_past = remain;

    while (remain)
    {
        vector<vector<int>> bounding = airflow(r, c);
        
        remain_past = remain;
        remain -= bounding.size();
        
        for (int i = 0; i < bounding.size(); ++i)
            cheese[bounding[i][0]][bounding[i][1]] = 0;
        ++cnt;
    }

    cout << cnt;    
}