치즈 2636

문제

접근 방법

가로, 세로 최대 100
쉽게 계산하기 위해 가로, 세로 모두 치즈가 있고 시간에 따라 하나씩 줄어드는 경우가 있다고 생각하면 100^4=100,000,000
1억이다. 그렇기에 BFS로 시간마다 탐색하여도 충분하다고 생각했다.
즉 시간마다 BFS를 하여 접촉면을 확인하는 것이다.
그 후 set을 이용하여 개수를 기록하고 접촉면을 녹여준다.

코드

#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    int H, W, cnt, time = 0;
    cin >> H >> W;
    vector<vector<bool>> map, visted;
    queue<pair<int, int>> bfs;
    set<pair<int, int>> cheese;
    for (int i = 0; i < H; ++i)
    {
        map.push_back(vector<bool>());
        for (int j = 0; j < W; ++j)
        {
            bool input;
            cin >> input;
            map[i].push_back(input);
        }
    }
    while (true)
    {
        cheese.clear();
        visted = vector<vector<bool>>(H, vector<bool>(W));
        bfs.push({0, 0});
        while (!bfs.empty())
        {
            pair<int, int> cur = bfs.front();
            bfs.pop();
            for (int i = 0; i < 4; ++i)
            {
                pair<int, int> next = {cur.first + dy[i], cur.second + dx[i]};
                if (next.first < 0 || next.second < 0 || next.first >= H || next.second >= W || visted[next.first][next.second])
                    continue;
                visted[next.first][next.second] = true;
                if (map[next.first][next.second])
                    cheese.insert(next);
                else
                    bfs.push(next);
            }
        }
        if (!cheese.empty())
        {
            cnt = cheese.size();
            ++time;
        }
        else
            break;
        for (auto i : cheese)
        {
            map[i.first][i.second] = false;
        }
    }
    cout << time << "\n"
         << cnt;
    return 0;
}

풀이

BFS를 시간별로 진행한다고 생각하면 쉽게 풀린다.
set을 이용하여 풀었지만, 글을 작성하며 생각해보니 이미 visted로 두 번 접근하는 것을 막았기에 굳이 set을 사용할 필요는 없었다. 또한 바로 치즈를 녹여줘도 해결됐겠다고 생각한다.

그래도 코드가 깔끔하게 나온 것 같아서 굳이 수정은 안 하려고 한다.