백준 2636번. 치즈(c++) / 시뮬

시뮬레이션 문제이다.

처음에 치즈 안에 있는 공기를 제외하고 겉에만 세야하는 것을 어떻게 해야할까 엄청 고민하다가...

어차피, 치즈는 가에 있을 수 없다는 조건을 보고 (0, 0)의 점을 큐에 넣고 외부의 공기를 모두 표시해주었다.

그리고 그 외부의 공기와 맞닿아 있는 치즈의 표면을 0으로 바꾸어 주었다.

 

 

코드 첨부

// 치즈
#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
int n, m;
int cheese[101][101] = {0, };
int visited[101][101] = {0, };
int sec = 0;
int final = 0; // 가장 마지막에 남은 치즈조각 수
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
// 외부의 공기들을 표시해주고 이와 인접한 치즈들을 0으로 만들어준다.
void bfs()
{
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
 
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        visited[x][y] = 1;
        q.pop();
 
        for(int t=0; t<4; t++){
            int nx = x+dx[t];
            int ny = y+dy[t];
            if(0<=nx && nx<n && 0<=ny && ny<m && !visited[nx][ny]){
                if(cheese[nx][ny]==0){
                    visited[nx][ny] = 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
 
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(visited[i][j]){
                for(int t=0; t<4; t++){
                    int nx = i+dx[t];
                    int ny = j+dy[t];
                    if(0<=nx && nx<n && 0<=ny && ny<m && cheese[nx][ny]==1){
                        cheese[nx][ny] = 0;
                    }
                }
            }
        }
    }
}
 
bool check()
{
    bool temp = false;
    int num = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(cheese[i][j]==1){
                temp = true;
                num++;
            }
        }
    }
    if(num != 0){
        final = num;
    }
    return temp;
}
 
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>cheese[i][j];
        }
    }
 
    while(1){
        if(!check()){ // 1이 아무것도 없을 경우
            break;
        }
 
        sec++;
 
        memset(visited, 0, sizeof(visited));
        bfs();
    }
 
    cout<<sec<<"\n";
    cout<<final<<"\n";
 
    return 0;
}

 

문제 첨부

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

2636번: 치즈

 

github 첨부

https://github.com/jungahshin/algorithm/blob/master/c:c%2B%2B/2636.cpp

jungahshin/algorithm