치즈 (feat. 백준, 2636번)

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

2636번: 치즈

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int R, C, dx[4], dy[4], arr[100][100];
bool visit[100][100];
int get_cheese_count(){
    register int count = 0;
    for(register int r = 0, c; r < R; ++r)
        for(c = 0; c < C; ++c)
            if(arr[r][c])       ++count;
    return count;
}
void bfs(register int x, register int y){
    memset(visit, false, sizeof(visit));
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    visit[x][y] = true;
    while(!q.empty()){
        auto pos = q.front(); q.pop();
        x = pos.first, y = pos.second;
        for(register int d = 0, nx, ny; d < 4; ++d){
            nx = x + dx[d], ny = y + dy[d];
            if(0 <= nx && nx < R && 0 <= ny && ny < C && !visit[nx][ny] && arr[nx][ny] == 0)
                visit[nx][ny] = true, q.push(make_pair(nx, ny));
        }
    }
}
void melt_cheese(){
    for(register int r = 1, c, d, nx, ny; r < R - 1; ++r)
        for(c = 1; c < C - 1; ++c)
            if(arr[r][c] == 1)
                for(d = 0; d < 4; ++d){
                    nx = r + dx[d], ny = c + dy[d];
                    if(visit[nx][ny]){
                        arr[r][c] = 0;
                        break;
                    }
                }

}
bool is_empty_cheese(){
    for(register int r = 0, c; r < R; ++r)
        for(c = 0; c < C; ++c)
            if(arr[r][c])
                return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    cin >> R >> C;
    for(register int r = 0, c; r < R; ++r)
        for(c = 0; c < C; ++c)
            cin >> arr[r][c];
    register int ans = 0, time = 0;
    while(++time){
        ans = get_cheese_count();
        bfs(0, 0);
        melt_cheese();
        if(is_empty_cheese())
            break;
    }
    cout << time << "\n" << ans;
    return 0;
}
// *&)*@*

 

1. 치즈의 총 개수를 구합니다.
2. 치즈의 가운데게 뚫린 구멍은 무시합니다. 즉 (0,0)부터 탐색했을때 인접한 곳이 "0" 이라면 치즈 바깥쪽의 구멍이므로 이 부분을 bfs로 탐색합니다.
3. 탐색이 끝나면 치즈를 찾습니다. 그리고 치즈의 인접한 곳에 2번에서 탐색했던 바깥쪽의 구멍이 있다면 0으로 변경 해줍니다.
4. 치즈가 없을때까지 2번과 3번을 반복합니다. 없다면 1번에서 구한 치즈의 총 개수를 함께 출력합니다.