https://www.acmicpc.net/problem/2636

접근 방식

문제를 보면서 bfs로 풀면 된다는건 바로 알아챘지만 겉면의 치즈를 어떻게 구분하는가를 많이 고민했다.

그림에서 공기 부분(하얀색)을 전부 BFS에 넣고 돌리면 될거라 생각했는데 치즈안의 구멍(얘도 마찬가지로 하얀색)은 공기가 없으니까 그럼 어떻게 해야하지 고민하다가 잘 보니까 그림에서 X인 부분도 공기라는 것을 깨달았다. 즉 벡터나 배열로 보면 (0, 0)의 좌표는 무조건 바깥 공기이기 때문에 (0, 0)을 BFS에 넣고 치즈가 없어질 때 까지 반복하면 될것이다를 깨달았다.

풀이

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

int n, m;
int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};
vector<vector<int>> vec(100, vector<int> (100));
vector<vector<bool>> visited(100, vector<bool> (100, false));
int ans1 = 0;
int ans2;
int temp;

void bfs() {
    while(true){
        queue<pair<int, int>> q;
        q.push({0,0});
        visited[0][0] = true;
        ans2 = temp;
        temp = 0;
        while(!q.empty()){
            auto [x, y] = q.front();
            q.pop();

            for(int i=0; i<4; i++){
                int nx = x + dirX[i];
                int ny = y + dirY[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < m && !visited[nx][ny]){
                    if(vec[nx][ny] == 1){
                        vec[nx][ny] = 0;
                        visited[nx][ny] = true;
                        temp++;
                    }
                    else if(vec[nx][ny] == 0){
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
        }
        if(temp != 0) ans1++;
        else break;
        fill(visited.begin(), visited.end(), vector<bool>(100, false));
    }
    cout << ans1 << "\n";
    cout << ans2;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> vec[i][j];
        }
    }
    bfs();

    
    return 0;
}

BFS안에서 while반복문을 두번 중첩한다. 첫번째 while문에서는 queue를 선언,
q에 (0,0)을 넣고 방문을 체크해준다. 두번째로 출력할 ans2 값에 temp를 저장하고, temp를 0으로 초기화한다. (temp는 사라질 치즈의 개수이다. 즉 치즈 겉면)

그 후 while문을 만들어 우리가 아는 bfs를 만들어주는데 공기와 치즈가 만나면 치즈가 있던 부분을 0으로 바꾸고 방문을 체크해주고 temp값을 1 증가시킨다. 공기와 공기를 만나면 방문을 체크하고 q에 넣어준다. 이러면 한번 bfs를 돌릴 때 마다 사라질 치즈의 갯수는 temp값에 저장된다. temp가 0이 아니면 ans1을 1 증가시키고(ans1은 치즈가 녹아 없어질 시간) 방문벡터를 초기화해준다. temp가 0이면 더 이상 사라질 치즈가 없기 때문에 break 해준다.

그러면 ans1에는 녹아 없어지는데 걸리는 시간이, ans2에는 녹아 없어지기전 마지막에 남아있던 치즈의 갯수가 잘 저장되어 있을 것이다.

시간복잡도

일단 BFS는 O(n * m)이고, 이 BFS가 최악의 경우(치즈가 가장자리를 제외한 모든공간을 채운 경우)에 MAX(n, m) 정도 반복되는 것 같다. 그래서 O(n^3)정도가 되지 않을까..