치즈

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
using namespace std;
int board[101][101];
int vis[101][101];
int N,M;
int day, save;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
queue<pair<int,int>> air;
queue<pair<int,int>> che;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 1)
                che.push({i,j});
        }
    if(che.empty()) goto finish;
    air.push({0,0});
    vis[0][0] = true;
    save = che.size();
    while(true)
    {
        queue<pair<int,int>> nextQ;
        // BFS 돌면서 다음에 이번에 공기와 접촉해서 갈 수있는 치즈를 녹이고 
        // 1좌표는 다음에 돌아야 하니까 다음 큐에 저장
        while(!air.empty())
        {
            auto cur = air.front(); air.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
                if(vis[ny][nx]) continue;
                if(board[ny][nx] == 1){
                    nextQ.push({ny,nx});
                    board[ny][nx] = 0;
                }
                else
                    air.push({ny,nx});
                vis[ny][nx] = true;
            }
        }
        air = nextQ;
        day++;
        /* 남은 치즈 개수 구하기 */
        int cnt=0;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(board[i][j] == 1) cnt++;
        if(cnt != 0) save = cnt;
        else break;
    }
    finish:;
    cout << day << '\n' << save << '\n';
}

• key point
  • 이번에 0좌표를 따라 도달할 수 있는 1의 좌표 = 이번에 녹을 치즈 & 다음에 돌아야 할 air