[백준 2636번] 치즈

문제 링크: https://www.acmicpc.net/problem/2636

2636번: 치즈

<문제 풀이> BFS

X로 표시된 곳엔 치즈가 없으니깐 X로 표시된 곳 중 한 곳에서 공기가 출발한다고 생각하고 BFS를 돌리면서 공기와 치지를 접촉시켜 보면 됩니다.

 

1. 공기는 이미 방문했던 곳을 다시 방문할 필요가 없다

2. 공기가 접촉한 적이 없는 치즈를 만나면 그곳을 한 시간 후 녹을 치즈로 바꾸고('c') 방문 체크를 합니다.

-> 그리고 한 시간 후 공기는 이 위치에서 다시 BFS를 진행하도록 임시 큐에 해당 좌표를 넣습니다.

-> 치즈가 녹으면 결국 그곳엔 공기가 생김 

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
#define X first
#define Y second
 
int dx[4] = {0, -1, 0, 1}; //0 == right, 1 == up, 2 == left, 3 == down
int dy[4] = {1, 0, -1, 0};
 
int n, m;
 
int cheeze[100][100];
bool visited[100][100];
void AirBFS() {
    queue<pair<int, int> > Q;
    Q.push({ 0, 0 });
    visited[0][0] = true;
    int time = 0; // 걸린 시간
    int last_cnt = 0; //마지막 녹기 한 시간 전에 남아있는 치즈 조각의 수 
    while (true) {
        queue<pair<int, int> > temp;
        bool flag = false; //한 시간 후 녹일 치즈가 있다면 true
        int cnt = 0; // 한 시간 후 녹일 치즈의 개수
        while (!Q.empty()) {
            auto cur = Q.front(); Q.pop();
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (visited[nx][ny] || cheeze[nx][ny] == 'c') continue; // 이미 방문했거나 치즈가 공기에 접촉했으면 무시
                if (cheeze[nx][ny] == 1) { // 공기에 접촉하지 않은 치즈이면
                    flag = true; 
                    cheeze[nx][ny] = 'c'; // 한 시간 후 치즈를 녹인다.
                    cnt++; // 한 시간 후 녹일 치즈의 개수 증가
                    temp.push({ nx, ny }); // 공기는 한 시간 후 녹을 치즈의 위치에서 다시 시작
                    visited[nx][ny] = true;
                }
                else { // 빈 공간이면 그냥 이동
                    Q.push({ nx, ny });
                    visited[nx][ny] = true;
                }
            }
        }
        if (!flag) { //한 시간 후 녹일 치즈가 없다면
            cout << time << '\n' << last_cnt;
            break;
        }
        last_cnt = cnt; //가장 최근에 녹인 치즈의 개수
        time++; // 한 시간 뒤
        Q = temp;
    }
}
 
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> cheeze[i][j];
        }
    }
    AirBFS();
    
    return 0;
}