[백준/C++] 2636번: 치즈

문제

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

---

문제 요약

N × M 크기의 정사각형 칸들로 이루어진 사각형 판이 있다.

 

판의 가장 자리에는 치즈가 놓여 있지 않고, 각 칸에는 치즈가 놓여 있거나 공기가 있다.

 

공기에 맞닿은 치즈는 한 시간이 지나면 녹아 없어진다.

 

치즈가 모두 녹아서 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아 있는 치즈 개수를 출력한다.

---

코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int n, m;

int board[110][110];
int temp[110][110];

// visited[i][j] : (i, j)가 공기인지 여부
bool visited[110][110];

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int main() {
    cin >> n >> m;

    bool is_cheese = false;

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

            if (board[i][j] == 1) {
                is_cheese = true;
            }
        }
    }

    int melt_time = 0;  // 모두 녹기까지 걸린 시간
    int last_cnt = 0; // 마지막으로 남아있던 치즈 양

    while (is_cheese) {
        int cheese_cnt = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1) {
                    cheese_cnt++;
                }
            }
        }

        // 더 이상 치즈가 없다면, 종료
        if (cheese_cnt == 0) {
            cout << melt_time << "\n" << last_cnt;
            break;
        }

        // 녹이기 전 상태의 치즈 개수 저장해두기
        last_cnt = cheese_cnt;

        // 녹이기 전 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = false;
                temp[i][j] = board[i][j];
            }
        }

        // 녹이기 시작
        melt_time++;

        queue<pair<int, int>> q;
        q.push({ 0, 0 });
        visited[0][0] = true;

        // 공기 BFS 탐색: (0, 0)이 항상 공기라고 가정하고 시작
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (!visited[nx][ny] && board[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.push({ nx, ny });
                }
            }
        }

        // 공기와 접촉한 치즈 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1) {
                    for (int d = 0; d < 4; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];

                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

                        if (visited[nx][ny]) {
                            temp[i][j] = 0; // 녹이기
                            break;
                        }
                    }
                }
            }
        }

        // board 갱신
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = temp[i][j];
            }
        }
    }

    return 0;
}

---

코드 설명

1. 판 정보를 입력 받는다.

 

2. 판에 치즈가 존재한다면, 녹이기 과정을 반복한다.

 

3. 치즈 개수를 세고, 더 이상 치즈가 없다면 녹이기 과정을 종료한다.

 

4. 녹이기를 진행하기 전에, 공기가 들어있는 칸을 BFS 탐색을 통해 체크한다.

 

5. 모든 칸을 탐색하면서, 공기가 들어있는 칸과 맞닿아 있는 치즈를 녹인다.

(녹일 때, 해당 칸에서 바로 없애면 제대로 결과가 도출되지 않음에 유의하여 임시 판을 이용한다.)