백준 및 코드포스

문제가 길어서 따로 사진을 첨부하진 않겠습니다.

직접 들어가서 읽어보시는 걸 추천드립니다.

결과적으로 구해야 하는 것은 바깥쪽의 공기와 치즈가 2번 이상 만나는지 입니다.

제 풀이 방법입니다.
1. 가장자리는 무조건 공기니까, 매번 (0,0)을 큐에 넣어준다.
2. 치즈 밖에 있는 공기만으로 공기의 접촉을 계산하니, bfs를 돌리며 치즈와 외곽의 공기가 만나면 1씩 더해준다.
3. 치즈가 공기와 2번 이상 접촉했으면 치즈를 공기로 바꿔준다.
4. vis 배열을 초기화 시킨 후, 1번부터 반복한다.

치즈가 전부 사라질 때까지 이를 반복해서 풀 수 있습니다.

코드에서 주석으로 핵심 ~,  ~  핵심 으로 표시해둔 부분이 다른 문제와 다른 부분입니다.

방문 여부만으로 continue를 시켜주면 치즈에 공기가 한 번만 닿고 그 이후엔 continue 되어 문제 해결이 불가능합니다.

치즈와 공기를 따로 생각해줘야합니다.

#include <iostream>
#include <queue>
using namespace std;

int board[101][101];
int vis[101][101];
int dx[4] = {1,-1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m;
int ans = -1,check = 1;
queue<pair<int,int> > Q;

void bfs() {
    check = 0;
            Q.push({0, 0}); //가장자리는 항상 공기임
            while(!Q.empty()){
                pair<int,int> cur = Q.front();
                Q.pop();
                int nx, ny;
                for(int dir = 0; dir < 4; dir++){
                    nx = cur.first + dx[dir];
                    ny = cur.second + dy[dir];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if(!board[nx][ny] && vis[nx][ny]) continue; //핵심 ~
                    if(board[nx][ny]) {
                        vis[nx][ny]++;
                        check = 1;
                        continue;
                    } // ~ 핵심
                    if(vis[nx][ny]) continue;
                    vis[nx][ny]++;
                    Q.push({nx,ny});
                }
            }
 
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(vis[i][j] >= 2) board[i][j] = 0; //2번 이상 접촉시 치즈가 녹음
            vis[i][j] = 0; //방문 초기화
        }
    }
    ans++;
    return;
}

int main() {
    ios::sync_with_stdio(0);
    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(check) { //check는 배열 board 안에 치즈가 남았는지 확인
        bfs();
    }
    cout<<ans;
}