[BOJ] 2638 : 치즈 (C++)

📖 백준 2638번 : https://www.acmicpc.net/problem/2638

조건

시간 제한	메모리 제한
1 초	128 MB

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다.

치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 인접한 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

---

풀이

  탐색을 반복하는 그래프 문제로 파악했다. 왜냐하면 단순히 0과 1로 구분되는 것이 아니라 영역을 구분해야 하기 때문에 탐색이 필요하다고 생각했다. 한 시간마다 치즈가 녹기 때문에 그래프가 계속해서 변경된다. 따라서 변경된 그래프에 알맞은 조건을 반복해서 체크해야 한다.

  모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다는 조건이 있으므로, (0, 0)에서 탐색을 시작해서 치즈와 외부영역을 구분했다. 탐색이 가능한 영역을 저장하고 영역과 2군데 이상 인접한 부분을 판별했다. dfs로 탐색하며 영역을 구분하고 visited배열에 true값을 가지는 i, j를 치즈의 외부 영역으로 생각했다. 치즈가 모두 녹아 없어지는지 판단하기 위해서 isEmpty함수를 구현해 while문의 조건으로 사용해서 구현을 마무리했다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
bool visited[101][101];
int space[101][101];

void dfs(int x, int y) {
    visited[x][y] = true;

    if (x - 1 >= 0 && space[x - 1][y] == 0 && !visited[x - 1][y]) //상
        dfs(x - 1, y);
    if (x + 1 < n && space[x + 1][y] == 0 && !visited[x + 1][y]) //하
        dfs(x + 1, y);
    if (y - 1 >= 0 && space[x][y - 1] == 0 && !visited[x][y - 1]) //좌
        dfs(x, y - 1);
    if (y + 1 < m && space[x][y + 1] == 0 && !visited[x][y + 1]) //우
        dfs(x, y + 1);
}

bool isEmpty() {// space가 비었다면 1을 반환
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (space[i][j] == 1) return 0;
        }
    }
    return 1;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> space[i][j];
        }
    }

    int ans = 0;
    while (!isEmpty()) {
        dfs(0, 0); // 외부 영역은 (0, 0)에서 탐색 가능한 범위에만 존재함.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (space[i][j] == 1) {
                    int cnt = 0;
                    //치즈와 인접한 상하좌우에 얼마나 외부 영역이 맞닿아 있는지 cnt값으로 판단
                    if (visited[i - 1][j]) cnt++;
                    if (visited[i + 1][j]) cnt++;
                    if (visited[i][j - 1]) cnt++;
                    if (visited[i][j + 1]) cnt++;

                    if (cnt >= 2) space[i][j] = 0;//cnt가 2이상이면 치즈는 녹는다.
                }

            }
        }
        fill(visited[0], visited[n], false);// 탐색을 반복할 것이기 때문에 visted배열을 초기화
        ans++;
    }
    cout << ans;// 모든 치즈가 녹아내릴 때까지 반복한 횟수가 답.

    return 0;
}