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

 

 

 

알고리즘 종류

    - 구현

    - BFS, DFS

 

 

 

사고 과정

    1. 치즈의 개수 구하기

    2. 가장자리를 표시하기

    3. 가장자리를 제거하기

    4. 1~3 반복

 

 

 

구현(C++)

#include <iostream>
#include <cstring>
#include <queue>
 
using namespace std;
 
 
int mat[101][101];
int isVisited[101][101];
 
int r, c;
int numCheese = 0;
 
int d[4][2] = {{1,0}, {0,1}, {-1,0},{0,-1}};
 
bool isValid(int y, int x){
    return (y>=0 && y<r) && (x>=0 && x<c);
}
 
void remove_edge(){
    
    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 i=0;i<4;i++){
            int ny = y + d[i][0];
            int nx = x + d[i][1];
            
            if(!isValid(ny, nx)) continue;
            if(isVisited[ny][nx]) continue;
            
            isVisited[ny][nx] = 1;
            
            // 치즈를 만나면 표시
            if(mat[ny][nx] == 1) mat[ny][nx] = -1;
            // 공기 부분이면 queue에 넣기
            else if(mat[ny][nx] == 0) q.push({ny, nx});
        }
        
    }
    
}
 
void count_cheese(){
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            // 치즈 개수 세기
            if(mat[i][j] == 1){
                numCheese ++;
            }
            
            // 표시된 치즈 제거
            if(mat[i][j] == -1){
                mat[i][j] = 0;
            }
        }
    }
}
 
void solution(){
    
    // 치즈 개수 임시 저장과 시간 표시
    int tmpNumCheese = 0;
    int time = 0;
    
    while(1){
        
        memset(isVisited, 0, sizeof(isVisited));
        numCheese = 0;
        
        count_cheese();
        
        remove_edge();
    
        // 치즈가 다 없어지면 종료
        if(numCheese == 0) break;
        
        time ++;
        
        tmpNumCheese = numCheese;
        
    }
    
    cout << time << endl;
    // 다 제거되기 전의 치즈 개수가 저장되어 있다.
    cout << tmpNumCheese << endl;
}
 
 
int main(void){
    
    cin >> r >> c;
    
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin >> mat[i][j];
        }
    }
    
    solution();
    
}
 
 
 

 

 

 

시행착오

    - BFS에서 그래프의 범위 밖인지 아닌지 확인하는 함수 isValid()에서 모든 값을 return true하는 실수를 해서 1시간 가량을 사용했다. 오랜만에 하니 return false를 해야되는데 그냥 false만 적어 놓았었다. 위에는 간단하게 만들어 놓았다.