[ baekjoon ] #2638 치즈

백준 #2638 치즈

문제 요약

---

• NxM의 모눈종이 위에 얇은 치즈가 존재(N이 세로, M이 가로)
• 이 치즈는 공기와 접촉하여 천천히 녹음
• 4변 중 2변 이상이 실내온도의 공기와 접촉한 치즈는 한시간만에 녹음
• 아래 <그림 1> 모양과 같은 치즈라면 C로 표시된 모든 치즈는 한 시간 후 사라짐
  
• <그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정
  → 녹지 않고 C로 표시된 치즈만 녹음
• 한 시간 후, 이 공간으로 공기가 유입되면 <그림 3>과 같이 C로 표시된 치즈들이 녹음
  
• 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정
• 치즈가 모두 녹는 데 걸리는 정확한 시간 구하기 !

💡Idea

1. 치즈 내부의 공기인지, 외부의 공기인지 어떻게 구분할까? (제일 어려웠음 ㅠㅠ)
   • 외부 공기와 내부 공기의 값을 다르게 주고 싶었으나 방법이 떠오르지 않았음,,
   • (0, 0)은 외부 공기이므로 (0, 0)과 연결된 공기들은 다 외부 공기로 판단 !
   • check 배열을 만든 후 외부 공기면 -1로 바꿈
2. 치즈가 다 녹아 없어지는 데 걸리는 시간은 어떻게 구할까?
   • 입력을 받을 때 cheese의 위치를 vector에 저장해두자.
   • 녹을 치즈가 남아있다면 치즈를 녹이고 외부의 공기와 내부의 공기를 연결해주자.
   • 이 과정을 한 번 수행할 때마다 시간을 증가시키자 !

[ SourceCode ]

#include <iostream>
#include <queue>
using namespace std;

int N, M, map[100][100], check[100][100];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우
queue <pair<int, int>> outAir; // 외부 공기

void air_change() {
    while(!outAir.empty()) { // 외부 공기 찾아서 check 값을 -1로
        int x = outAir.front().first;
        int y = outAir.front().second;
        check[x][y] = -1;
        outAir.pop();

        for(int i=0; i<4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(map[nx][ny] == 0 && check[nx][ny] == 0) {
                check[nx][ny] = -1;
                outAir.push({nx, ny});
            }
        }
    }
}

void remove_cheese(vector <pair<int, int>> &cheese) {
    for(int i=0; i<cheese.size(); i++) {
        int x = cheese[i].first;
        int y = cheese[i].second;
       
        int air = 0;
        for(int j=0; j<4; j++) {
            int nx = x + dir[j][0];
            int ny = y + dir[j][1];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(map[nx][ny] == 0 && check[nx][ny] == -1) {
                air++;
            }
        }

        if(air >= 2) {
            map[x][y] = 0;
            outAir.push({x, y});
            cheese[i] = {-1, -1};
        }
    }
}

int main() {
    cin >> N >> M;

    vector <pair<int, int>> cheese; // 녹일 치즈
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) {
                cheese.push_back({i, j});
            }
        }
    }

    // 1. 외부 공기, 내부 공기 구분하기
    outAir.push({0, 0});
    check[0][0] = -1;
    air_change();

    // 2. 녹을 수 있는 치즈 찾아 녹이고 외부 공기와 내부 공기 연결
    int cnt = 0;
    while(1) {
        remove_cheese(cheese);
        if(outAir.empty()) {
            cout << cnt;
            break;
        }
        air_change();
        cnt++;
    }

    return 0;
}

Feedback

---

1. 치즈의 내부인지를 어떻게 판단할지를 고민하다보니 어려웠다.
   → 문제에서 모눈종이의 맨가장자리에는 치즈가 놓이지 않는다는 조건을 주목해야한다 !
   → 이걸 어떻게 이용할까? 고민해보면 가장 자리의 공기들을 연결하면 된다는 생각을 할 수 있다.
   → 조건이 힌트가 될 수 있으니 잘 생각해보자 !!!