[BOJ 2636] 치즈

2636번: 치즈

 

1. 문제

 

아래 그림과 같이 c로 표시된 부분은 녹아서 빈 칸이 되고, 빨간색으로 표시한 치즈의 가장자리가 새로운 'c'가 된다.

 

 

3시간 후 모든 치즈가 녹아 없어졌고, 모두 녹기 1시간 전 치즈의 개수는 <그림 3>에서 확인할 수 있듯 5개이다.

그렇기 때문에 첫 줄에는 3, 두 번째 줄에는 5를 출력한다.

 

2. 구현 아이디어

 

이번 문제에서는 치즈 안에 있는 구멍(위 그림 속 빨간 영역)과 치즈 밖의 공간을 어떻게 구분할지가 핵심 포인트이다.

치즈 안의 공간을 단순히 0이라고 하고 인접한 칸에 0이 있다고 c로 처리하면 안된다.

 

( 구멍을 어떻게 처리할지 좋은 방법이 떠오르지 않아 결국 다른 사람의 풀이를 참고하였다 🥲 )

💡 치즈 밖의 공간만 처리하는 방법: (0, 0)부터 시작해서 BFS를 돌며 0인 칸을 찾는다.

 

이렇게 할 경우 치즈 안의 공간은 1인 칸들로 둘러싸여 있기 때문에 BFS에 걸리지 않게 되고 치즈 밖의 공간만 찾을 수 있게 된다.

 

정답을 찾기 위한 나머지 과정을 글로 정리하면 아래와 같다.

1. (0, 0)부터 시작해서 BFS를 돌며 0인 칸을 찾는다.
2. check 배열을 사용하여 치즈 밖의 공간인지 구분한다.
3. 2중 반복문으로 판 전체를 돌면서 1인 칸들 중 인접한 칸 중 치즈 밖의 공간이 있다면(= check[nx][ny]가 true), 해당 칸을 0으로 바꾼다.
4. 위 과정을 판에 1인 칸이 남아있지 않을 때까지 1~3번 과정을 while문으로 반복한다. while문을 돌 때마다 t를 1씩 더해줘서 시간을 count하고, 치즈 조각의 개수를 갱신하여 가장 마지막에 남은 치즈 조각의 개수를 저장한다.

 

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int r, c; // 행, 열

int v[101][101];
bool check[101][101];

int t; // 모두 녹아서 없어지는 데 걸리는 시간
int ret; // 모두 녹기 한 시간 전에 남아있는 치즈 조각

int cx, cy, nx, ny;
int dx[4] = {0, 1, 0, -1};
int dy[4] = { -1, 0, 1, 0};

// 판에 있는 치즈의 개수를 세는 함수
int countCheese() {
    int cheese = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (v[i][j] == 1) cheese++;
        }
    }

    return cheese;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> r >> c;

    // 입력
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> v[i][j];
        }
    }

    // while문을 1번 돌 때마다 1시간이 지남
    while (true) {
        int tmp = countCheese();

        // 남아있는 치즈가 없다면 while문 종료
        if (tmp == 0) break;
            // 현재 치즈의 개수를 ret에 저장
        else ret = tmp;

        queue<pair<int, int>> q;
        memset(check, false, sizeof(check));

        // (0, 0)부터 시작해서 치즈 밖의 공간을 찾는다
        q.push({0, 0});
        check[0][0] = true;
        while (!q.empty()) {
            cx = q.front().first;
            cy = q.front().second;
            q.pop();

            for (int i = 0; i < 4; ++i) {
                nx = cx + dx[i];
                ny = cy + dy[i];

                if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;

                if (!check[nx][ny] && v[nx][ny] == 0) {
                    check[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        
        // 치즈가 공기에 닿아 녹는다
        // 가장자리에는 치즈가 없으므로 1부터 시작
        for (int i = 1; i < r-1; ++i) {
            for (int j = 1; j < c-1; ++j) {
                // 치즈가 없는 칸은 skip
                if (v[i][j] == 0) continue;

                // 치즈이면서 인접한 위치 중 하나라도 밖이면 녹는다
                for (int k = 0; k < 4; ++k) {
                    nx = i + dx[k];
                    ny = j + dy[k];

                    // v[nx][ny] == 0으로 하면 안됨
                    if (check[nx][ny]) {
                        // 치즈가 녹는 것을 표현
                        v[i][j] = 0;
                        break;
                    }
                }
            }
        }
        t++;
    }

    cout << t << "\n";
    cout << ret << "\n";
    return 0;
}

Reference

https://regularmember.tistory.com/80