[BOJ/2636번치즈] c++ / BFS

문제

공기에 둘러싸인 치즈가 녹아 없어질 때까지 걸리는 최소 시간을 구하는 문제

-치즈에 둘러싸인 구멍으로는 공기가 통하지 않음

 

생각

공기를 모두 큐에 푸쉬해서 공기와 맞닿은 치즈 녹이기

녹은 치즈 자리에 0 채우기

치즈 개수가 0이 될때까지 반복문 돌리기

 

문제풀이

1.전체 치즈 개수 세기

2.치즈 개수가 0일 될 때까지 BFS 탐색 ( 탐색할 때 마다, vis 초기화 )

3.배열의 외곽선을 모두 큐에 푸쉬 + 방문표시 ( 항상 공기가 있는 자리 )

4.기준칸의 상하좌우를 탐색

4-1.공기가 있으면, 큐에 푸쉬 + 방문표시

4-2.치즈가 있으면, 치즈를 녹임 + 방문표시 ( -> 치즈 배열칸에 0 대입 )

4-3. cnt 값 반환 ( 탐색 전, 이전의 cnt 값을 prev_cnt 저장해둠 )

5.BFS 탐색 횟수와 prev_cnt 값 출력

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define X first
#define Y second
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int board[101][101];
int vis[101][101];
int N, M, cnt=0, prev_cnt=0, t=0;
int BFS() {
    memset(vis, 0, sizeof(vis));
    prev_cnt = cnt;
    queue<pair<int, int>> Q;
    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < M; j++ ) {
            if ( i == 0 || i == N-1  || j == 0 || j == M-1 ) {
                vis[i][j] = 1;
                Q.push({i, j});
            }
        }
    
    while(!Q.empty()) {
        pair<int, int> 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 || nx >= N || ny < 0 || ny >= M ) continue;
            if ( !board[nx][ny] && !vis[nx][ny] ) {
                vis[nx][ny] = 1;
                Q.push({nx, ny});
            }
            if ( board[nx][ny] && !vis[nx][ny] ) {
                board[nx][ny] = 0;
                vis[nx][ny] = 1;
                cnt--;
            }
        }
    }
    return cnt;
    
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for ( int i = 0; i < N; i++ )
        for ( int j = 0; j < M; j++ ) {
            cin >> board[i][j];
            if ( board[i][j] == 1 )
                cnt++;
        }
    
    cnt = BFS();
    t = 1;
    while ( cnt ) {
        t++;
        BFS();
    }
    cout << t << "\n" << prev_cnt;

}