BOJ - 2638 치즈

치즈가 전부 녹는데 걸리는 시간을 구하는 문제이다.

문제 해결 전략
가장 중요한 부분은 치즈의 외부와 내부를 구분하는 것이다.

치즈 내부는 공기와 접해 있더라도 녹지 않는다는 조건이 있다.

따라서 0,0부터 bfs를 진행한다.

상하좌우를 탐색한 후 공기일 때만 큐에 넣어주며 다음 진행할 것을 예약한다.

그리고 공기가 아닐 때에는 해당 부분에 ++해 주며 맞닿은 면이 몇개인지 체크를 해 준 후, 탐색을 마치고 나면 맞닿은 면이 두개 이상인 곳을 공기로 바꾸어 준다.

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

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int xp[4] = {-1,0,1,0};
int yp[4] = {0,-1,0,1};

int bfs(vector<vector<int>> &visited, vector<vector<int>> &v){
    queue<pair<int,int>> q;
    q.push(make_pair(0,0));
    visited[0][0] = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int xx = x + xp[i];
            int yy = y + yp[i];
            if(xx < 0 || xx >= v.size() || yy < 0 || yy >= v[0].size())
                continue;
            if(visited[xx][yy] == 1)
                continue;
            if(v[xx][yy] != 0) {
                v[xx][yy]++;
                continue;
            }
            visited[xx][yy] = 1;
            q.push(make_pair(xx,yy));
        }
    }
    int cnt = 0;
    for(int i=0;i<v.size();i++){
        for(int j=0;j<v[i].size();j++){
            if(v[i][j] == 0)
                continue;
            if(v[i][j] > 2) {
                cnt++;
                v[i][j] = 0;
            }else{
                v[i][j] = 1;
            }
        }
    }
    return cnt;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v;
    for(int i=0;i<n;i++){
        vector<int> w;
        for(int j=0;j<m;j++){
            int k;
            cin >> k;
            w.push_back(k);
        }
        v.push_back(w);
    }

    int cnt = 0;
    while(1){
        vector<vector<int>> visited;
        for(int i=0;i<n;i++){
            vector<int> tmp(m);
            visited.push_back(tmp);
        }
        if(bfs(visited, v) == 0)
            break;
        cnt++;
    }

    cout << cnt << "\n";
    return 0;
}

출처
https://www.acmicpc.net/problem/2638