[백준] 2636번 : 치즈

문제

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

2636번: 치즈

 

주안점

BFS로 보통은 치즈를 순회할 생각을 하지만 치즈가 없는 구간을 순회하며 체크 후 치즈 삭제

 

 

 

구조

BFS로 체크해가면서 순회하고 삭제하고 순회하고 삭제하고

 

 

코드

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v;
int visited[104][104], a[104][104];
int row,col,x,y,cnt,leave;

int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};

int main() {
    cin>>row>>col;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            cin>>a[i][j];
        }
    }
    queue<pair<int,int>> q;

    while(true){
        memset(visited,0,sizeof(visited));
        v.clear();
        visited[0][0] = 1;
        q.push({0,0});
        while(q.size()){
            tie(y,x) = q.front(); q.pop();
            for(int k=0; k<4; k++){
                int ny = y+dy[k];
                int nx = x+dx[k];
                if(ny>=row || nx>=col || ny<0 || nx<0) continue;
                if(visited[ny][nx]) continue;
                if(a[ny][nx] == 1) {
                    visited[ny][nx] = 1;
                    v.push_back({ny,nx});
                    continue;
                }
                visited[ny][nx] = 1;
                q.push({ny,nx});
            }
        }
        if(v.size() == 0) break;
        leave = v.size();
        for(pair<int,int> b : v)
            a[b.first][b.second] = 0;
        cnt++;
    }
    cout<<cnt<<"\n";
    cout<<leave<<"\n";
}