백준 2636 치즈

문제

2636 치즈 문제 링크
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.

치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 치즈의 위치가 주어졌을 때, 첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

풀이

BFS로 풀었다.
(0, 0)은 항상 치즈가 없는 공기칸이기 때문에 (0, 0)에서 시작해서 BFS로 탐색한다. 한 번 BFS 탐색할 때 1을 만나면 1 → 0(= 치즈가 녹아서 사라짐)으로 바꾸고, 녹은 치즈의 개수를 누적해서 더해 반환한다.

BFS는 cheese의 개수가 0이 될 때까지 반복하는데, BFS를 실행한 횟수가 모두 녹아서 없어지는 데 걸리는 시간이고, 마지막 BFS에서 반환한 녹은 치즈 개수가 모두 녹기 한 시간 전에 남아있는 치즈가 된다.

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
int cheese = 0;
vector<vector<int>> map;
int di[]={0,0,-1,1};
int dj[]={-1,1,0,0};


int BFS(int i, int j) {
    vector<vector<bool>> visit(n, vector<bool>(m, false));
    queue<pair<int, int>> que;
    que.push(make_pair(i, j));
    visit[i][j] = true;
    int cnt = 0;
    while (!que.empty()) {
        int ii = que.front().first;
        int jj = que.front().second;
        que.pop();
        for (int k = 0; k < 4; k++) {
            int ni = ii + di[k];
            int nj = jj + dj[k];
            if (ni < 0 || nj < 0 || ni >= n || nj >= m) {
                continue;
            }
            if (visit[ni][nj]) {
                continue;
            }
            if (map[ni][nj] == 0) {
                que.push(make_pair(ni, nj));
                visit[ni][nj] = true;
            } else {
                cheese--;
                cnt++;
                map[ni][nj] = 0;
                visit[ni][nj] = true;
            }
        }
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    map.resize(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) {
                cheese++;
            }
        }
    }

    int ans = 0;
    int tmp;
    while (cheese > 0) {
        tmp = BFS(0, 0);
        ans++;
    }
    cout << ans << '\n' << tmp;

    return 0;
}

매번 (0, 0)에서 시작하면 시간 초과가 나오지 않을까해서 녹는 치즈의 위치를 추적할까도 고민했었는데 다행히? 바로 통과되었다😀