문제

2636번: 치즈

풀이

공기와 접촉된 치즈를 찾는 작업과 공기와 접촉된 치즈가 녹아 없어지는 작업을 분리하여 실행해야 한다.
찾는 작업과 녹아 없어지는 처리를 동시에 하게 될 경우 녹아 없어져 생긴 빈자리로 인해 올바른 결과가 나오지 않기 때문이다.

공기와 접촉된 치즈를 찾는 작업find()은 bfs를 통해 찾았다. 외부 0과 인접하는 1을 찾아 buffer에 추가하면
녹아 없어지는 작업melt()을 할때 그 buffer에 담겨있는 1들을 0으로 변경한다.

문제에서 모든 치즈가 녹기 직전에 남아있는 치즈의 개수를 구해야 하므로 melt()에서 buffer의 크기를 반환값으로 한다.

치즈가 모두 녹았는지 확인하는 작업을 위해 고민을 했었는데
그냥 판위를 탐색하며 모두 0인지 확인하는 것으로도 시간이 충분했다.

코드

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

#define x first
#define y second

using namespace std;

int w, h;
vector<vector<int>> plate;
vector<pair<int, int>> buffer;
vector<pair<int, int>> dir { {0,1}, {1,0}, {-1, 0}, {0, -1} };

bool OOB(int x, int y) { return x < 0 || x >= h || y < 0 || y >= w; }

void find()
{
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(h, vector<bool>(w, false));
    int cnt = 1;
    q.push({0, 0});
    visited[0][0] = true;

    while(!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();

        for (int i=0; i<4; ++i)
        {
            int nx = cur.x + dir[i].x;
            int ny = cur.y + dir[i].y;

            if (OOB(nx, ny) || visited[nx][ny])
                continue;

            if (plate[nx][ny] == 0)
                q.push({nx, ny});

            else
                buffer.push_back({nx, ny});
            
            visited[nx][ny] = true;
        }
    }

}

int melt()
{
    for (auto pos : buffer)
        plate[pos.x][pos.y] = 0;

    return buffer.size();
}

bool checkEnd()
{
    for (int i=0; i<h; ++i)
        for (int j=0; j<w; ++j)
            if (plate[i][j] == 1)
                return false;

    return true;
}

int main()
{
    cin >> h >> w;
    plate.assign(h, vector<int>(w));
    for (int i=0; i<h; ++i)
    {
        for (int j=0; j<w; ++j)
        {
            cin >> plate[i][j];
        }
    }
    
    int time = 0;
    int last;
    while(!checkEnd())
    {
        find();

        last = melt();

        buffer.clear();
        ++time;
    }

    cout << time << endl;
    cout << last << endl;
    return 0;
}

모든 치즈가 녹았는지에 대한 확인을 빠르게 하고 싶어 이것저것 고민을 했었는데 그러다가 오히려 반례에 막혔다.

참고

반례
https://www.acmicpc.net/board/view/35416