[boj] 백준 2638 치즈 (c++) - BFS

[문제]

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

2638번: 치즈

 

[풀이]

치즈는 내부 공기에 의해서는 녹지 않으므로 외부 공기와 내부 공기를 구분해주어야 한다.

문제 조건에서 가장 자리에는 치즈가 놓이지 않는다고 했으므로 (0,0)부터 탐색을 진행하면 외부 공기에 대해서만 치즈에 닿는 면을 증가시켜줄 수 있다. 벽이면 계속 탐색을 진행, 치즈면 닿는 면을 증가시켜준 후, 탐색이 끝나면 녹을 수 있는 치즈를 녹인다. 그 후 다시 bfs를 돌려 치즈가 모두 녹을 때까지 위 과정을 반복한다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n, m;
int board[101][101];
bool visited[101][101];
int cheese[101][101];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
int ans;

void bfs(){
    queue<pair<int, int>> q;
    visited[0][0] = true;
    q.push({0, 0});

    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr < 0 || nc < 0 || nr >= n || nc >= m || visited[nr][nc]) continue;

            if(board[nr][nc]==0){
                visited[nr][nc] = true;
                q.push({nr, nc}); //벽이면 탐색을 계속 함.
            }
            else if(board[nr][nc]==1){
                cheese[nr][nc]++; //외부와 공기와 접촉
            }
        }
    }
}

void melt(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(cheese[i][j]>=2){ //2면 이상 외부공기와 접촉해있으면
                board[i][j] = 0;
            }
        }
    }
}

bool check(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(board[i][j]){
                return false; //치즈가 남아있으면
            }
        }
    }
    return true;
}

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

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

    while(true){
        if(check()){
            break;
        }
        memset(visited, false, sizeof(visited));
        memset(cheese, 0, sizeof(cheese));
        bfs();
        melt();
        ans++;
    }

    cout << ans;
}