[백준][C++] 2638 치즈

 

 

 

알고리즘 종류

    - 구현

    - BFS

 

 

 

사고 과정

    1. (0,0)에서 시작해서 BFS로 치즈인 부분을 찾으면, map 자료형에 좌료를 넣고 개수를 센다.

    2. map에 넣은 것 중에 value가 2이상(공기 중에 노출된 면이 2개 이상)이면 좌표의 치즈를 없앤다.

    3. 치즈의 총 개수가 0일 될 때까지 1번과 2번을 반복한다. 

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
 
using namespace std;
 
int n, m;
int numCheese = 0;
int time=0;
 
int mat[101][101];
int isVisited[101][101];
 
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
map<pair<int, int>, int> numExposed;
 
bool isValid(int y, int x){
    return (y>=0 && y<n) && (x>=0 && x<m);
}
 
// 공기 닿은 치즈의 면의 개수 구하기  
void findExposed(){
    queue<pair<int, int> > q;
    q.push({0,0});
    isVisited[0][0] = 1;
    
    while(!q.empty()){
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        
        for(int d=0; d<4; d++){
            int ny = y + dir[d][0];
            int nx = x + dir[d][1];
            
            // 공기 중에 닿는 면 개수를 센다.  
            if(mat[ny][nx] == 1){
                numExposed[{ny, nx}]++;
            }
            
            if(isVisited[ny][nx]) continue;
            if(!isValid(ny, nx)) continue;
            
            isVisited[ny][nx] = 1;
            
            // 치즈가 아닐 때만 queue에 넣어서 BFS를 동작시킨다. 
            if(mat[ny][nx] == 0)
                q.push({ny, nx});
        }
    }
}
 
void solution(){
    
    while(1){
        // 초기화 
        numExposed.clear();
        memset(isVisited, 0, sizeof(isVisited));
        
        if(numCheese == 0) return;
        time ++; 
        
        // 공기와 접촉한 치즈의 면의 개수를 센다.  
        findExposed();
        
        // 공기 중에 접촉한 치즈의 면이 2개 이상이면 치즈를 제거한다. 
        map<pair<int, int>, int> ::iterator iter;
        for(iter=numExposed.begin(); iter!=numExposed.end(); iter++){
            if(iter->second >= 2){
                mat[(iter->first).first][(iter->first).second] = 0;
                numCheese--;
            }
        }
    }
}
 
 
int main(void){
    
    cin >> n >> m;
    
    int state;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> state;
            mat[i][j] = state;
            if(state) numCheese ++ ;
        }
    }
    
    solution();
    
    cout << time;
}
 
 
 

 

 

 

시행착오

    - 캐슬 디펜스에 이어서 map으로 중복된 좌표를 다루어 보았다. 나름 괜찮은 방법 같다.