[백준 2638번] 치즈

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

2638번: 치즈

<문제 풀이> BFS

1. BFS로 (0,0)에서 공기를 출발시킨다.

2. 공기가 치즈를 2번 터치하는지 체크하고 만약 2번 터치를 했다면 임시 큐에 치즈가 녹을 자리를 넣어준다

3. 공기 BFS에 큐가 모두 비게 되면 임시 큐에 저장했던 치즈가 녹은 자리를 다시 공기 큐에 넣어준다

-> 치즈가 녹은 자리는 다시 공기가 채워지므로 공기의 다음 시작 위치가 됨

 

<C++ 소스 코드>

#include <iostream>
#include <utility>
#include <queue>
using namespace std;
 
#define X first
#define Y second
 
int N, M;
int board[100][100];
bool visited[100][100];
int hour[100][100];
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
 
void bfs() {
    int res = 0;
    queue<pair<int, int> >Q;
    Q.push({ 0, 0 });
    visited[0][0] = true;
    while (true) {
        queue<pair<int, int> > temp; //치즈가 녹은 자리에서 공기 BFS 시작
        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 (board[nx][ny] == 1) {
                    if (visited[nx][ny]) { //공기가 치즈를 2번 터치하면
                        temp.push({ nx,ny });
                        board[nx][ny] = 0;
                        hour[nx][ny] = hour[cur.X][cur.Y] + 1;
 
                    }
                    else {
                        visited[nx][ny] = true;
                    }
                }
                else {
                    if (!visited[nx][ny]) {
                        Q.push({ nx, ny });
                        visited[nx][ny] = true;
                    }
                }
 
            }
        }
        if (temp.size() == 0) { //더이상 남아있는 치즈가 없는 경우
            cout << res;
            return;
        }
        res++;
        while (!temp.empty()) {
            Q.push(temp.front()); temp.pop();
 
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
        }
    }
    bfs();
    
 
    return 0;
}