[PS] 백준 2636 치즈

이번에는 백준 2636번 치즈 문제를 풀어보았습니다.

이 문제는 치즈가 한 시간마다 바깥 공기와 맞닿은 부분부터 녹을 때,

모든 치즈가 다 녹는 데 걸리는 시간과 다 녹기 한 시간 전 치즈 개수를 구하는 문제입니다.

처음에는 치즈를 기준으로 탐색하려고 했지만,

실제로는 공기에서 시작해서 바깥쪽 치즈를 찾는 방식으로 접근해야 훨씬 자연스럽게 풀 수 있었습니다.

---

문제 설명

판 위에는 치즈가 놓여 있고, 치즈가 없는 칸은 공기입니다.

여기서 중요한 조건은 다음과 같습니다.

• 바깥 공기와 맞닿은 치즈는 한 시간이 지나면 녹는다.
• 치즈 내부의 구멍은 처음부터 공기가 아니다.
• 하지만 바깥 치즈가 녹아서 구멍이 열리면, 그때부터 그 안도 공기가 된다.

즉, 매 시간마다 현재 바깥 공기와 접촉한 치즈만 녹는다는 점이 핵심입니다.

문제에서는

1. 치즈가 모두 녹는 데 걸리는 시간
2. 모두 녹기 한 시간 전에 남아 있던 치즈 칸 수

를 출력하면 됩니다.

---

풀이 아이디어

이 문제는 치즈를 기준으로 보면 오히려 복잡해집니다.

왜냐하면 치즈 내부의 구멍은 처음에는 공기가 아니고,

매 시간이 지날 때마다 바깥 공기 영역이 달라지기 때문입니다.

그래서 이 문제는 공기에서 출발하는 DFS로 접근했습니다.

구체적으로는,

• (0, 0)에서 시작해 바깥 공기 영역을 DFS로 탐색하고
• 탐색 도중 만나는 치즈는 “이번 시간에 녹을 외곽 치즈”로 저장하고
• 그 치즈들을 모두 0으로 바꾼 뒤
• 다시 같은 과정을 반복

하는 방식입니다.

즉, 매 시간마다

바깥 공기 탐색 → 외곽 치즈 수집 → 치즈 제거

를 반복하는 구조입니다.

---

V1 코드

#include <bits/stdc++.h>
using namespace std;
int inp_map[100][100];
int visited[100][100];
vector<pair<int, int>> cheese;
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};
int cnt;
int cheese_size;
int N,M;

void dfs(int y, int x) {
    if (inp_map[y][x] == 1) {
        cheese.push_back(make_pair(y, x));
        visited[y][x] = 1;
        return;
    }
    visited[y][x] = 1;

    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
        if (visited[ny][nx] == 0) dfs(ny, nx);
    }
}

int main() {

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> inp_map[i][j];
        }
    }

    while(true) {
        fill(&visited[0][0], &visited[0][0] + 100 * 100, 0);
        dfs(0, 0);
        if (cheese.empty()) break;
        cnt++;
        cheese_size = cheese.size();
        for (pair<int, int> chee : cheese) {
            int y = chee.first;
            int x = chee.second;
            inp_map[y][x] = 0;
        }
        cheese.clear();
    }

    cout << cnt << "\n" << cheese_size << "\n";
    return 0;
}

---

풀이 흐름

1. 입력으로 판의 크기와 치즈 상태를 받는다.
2. 반복문을 돌면서 매 시간마다 visited를 초기화한다.
3. (0, 0)에서 DFS를 시작해 바깥 공기 영역을 탐색한다.
4. DFS 중 치즈를 만나면 cheese 벡터에 저장한다.
5. DFS가 끝난 뒤 cheese가 비어 있으면 모든 치즈가 녹은 것이므로 종료한다.
6. 그렇지 않다면 시간 cnt를 증가시킨다.
7. 이번에 녹을 치즈 개수를 cheese_size에 저장한다.
8. cheese에 담긴 좌표들을 모두 0으로 바꾼다.
9. cheese를 비우고 다음 시간을 반복한다.
10. 마지막에 총 시간과 마지막 치즈 개수를 출력한다.

---

구현 포인트

1. 치즈가 아니라 공기를 기준으로 생각하기

이 문제에서 가장 중요했던 포인트는 이 부분이었습니다.

처음에는 치즈를 기준으로 DFS를 생각할 수 있는데,

실제로는 공기를 기준으로 바깥에서부터 탐색해야 외곽 치즈를 정확하게 찾을 수 있습니다.

코드에서도 DFS를 (0, 0)에서 시작했습니다.

dfs(0, 0);

판의 가장자리는 치즈가 없다고 했기 때문에,

(0, 0)은 항상 바깥 공기라고 볼 수 있습니다.

즉, 바깥 공기에서 출발해서 닿을 수 있는 영역만 탐색하면,

그 과정에서 만나는 치즈가 바로 “이번 시간에 녹을 치즈”가 됩니다.

---

2. DFS에서 치즈를 만나면 저장만 하고 종료

DFS 함수 안에서 현재 칸이 치즈라면 더 깊게 탐색하지 않고,

그 좌표만 저장한 뒤 반환합니다.

if (inp_map[y][x] == 1) {
    cheese.push_back(make_pair(y, x));
    visited[y][x] = 1;
    return;
}

이 부분이 중요한 이유는,

치즈 내부까지 들어가는 것이 아니라 공기와 맞닿은 외곽 치즈만 수집해야 하기 때문입니다.

즉, 공기 DFS를 하다가 치즈를 만나면 “이번에 녹을 대상”으로만 표시하고 끝내는 구조입니다.

---

3. 이번 시간에 녹을 치즈를 벡터에 모아두기

DFS를 돌면서 찾은 외곽 치즈는 cheese 벡터에 저장합니다.

vector<pair<int, int>> cheese;

이렇게 모아둔 뒤, DFS가 모두 끝나면 한 번에 제거합니다.

for (pair<int, int> chee : cheese) {
    int y = chee.first;
    int x = chee.second;
    inp_map[y][x] = 0;
}

즉, 탐색 중 바로 없애는 것이 아니라,

이번 시간에 녹을 치즈를 전부 수집한 뒤 한꺼번에 녹이는 방식입니다.

---

4. 시간과 마지막 치즈 개수 저장

문제에서는

• 총 몇 시간이 걸렸는지
• 마지막 한 시간 전에 치즈가 몇 개 있었는지

를 함께 출력해야 합니다.

그래서 치즈가 남아 있는 동안만 시간을 증가시키고,

cnt++;

이번에 녹는 치즈 개수를 따로 저장했습니다.

cheese_size = cheese.size();

이 값은 반복이 끝났을 때

“모두 녹기 직전의 치즈 개수”가 됩니다.

---

5. 매 반복마다 visited 초기화

한 시간이 지나고 판 상태가 바뀌면,

다음 시간에는 다시 바깥 공기부터 새롭게 탐색해야 합니다.

그래서 매 반복마다 visited 배열을 초기화했습니다.

fill(&visited[0][0], &visited[0][0] + 100 * 100, 0);

이렇게 해야 이전 DFS 결과가 다음 시간 탐색에 영향을 주지 않습니다.

---