[2636] 치즈

문제

치즈가 있을 때 공기와 닿은 치즈는 녹아서 사라진다.
치즈의 맵이 주어질 때 사라지는데 걸리는 시간과 사라지기 직전에 있던 치즈의 숫자를 출력하라.

Solution

최외곽은 항상 공기라고 볼 수 있기 때문에 최외곽에서 그래프 탐색 알고리즘(BFS/DFS)를 돌려 공기를 구하고 치즈가 공기와 닿았는지 직접적으로 확인하면 되는 간단한 문제였다.

solution code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n,m;
int map[101][101];
bool visit[101][101];
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

void init(){
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) visit[i][j] = 0;
}

int main(){
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    int cnt = 0;
    bool flag = 1;
    int bf = 0;
    while(flag){
        flag = 0;
        init();
        cnt++;
        queue<pair<int,int>>q;
        q.push({0,0});
        while(!q.empty()){
            int cx = q.front().first;
            int cy = q.front().second;
            q.pop();
            for(int i=0; i<4; i++){
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if(nx < 0 || ny <0 || nx >= n || ny>=m)continue;
                if(map[nx][ny] || visit[nx][ny])continue;
                visit[nx][ny] = 1;
                q.push({nx,ny});
            }

        }
        int cheese = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j] == 0) continue;
                for(int k=0; k<4; k++){
                    if(!visit[i+dx[k]][j+dy[k]])continue;
                    map[i][j] = 0;
                    flag = 1;
                    cheese++;
                    break;
                }
            }
        }
        if(flag){
            bf=cheese;
        }
    }
    cout << cnt-1 << '\n' << bf;

    return 0;
}