[백준/Baekjoon] 2638 치즈 C++ :: BFS & Graph & Implementation

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

2638번: 치즈

---

1. Logic

- 이 문제를 풀기 위한 가장 핵심은 공기가 치즈 외부에 있는 공기인지 내부에 있는 공기인지를 확인해야 한다.

문제의 조건에서 모눈종이의 가장자리는 항상 공기가 있다고 했다. 그렇기 때문에 가장자리부터 즉 (0,0)은 항상 공기이기 때문에 (0, 0)에서부터 BFS를 돌며 치즈를 녹일 수 있는 공기인지 아닌지를 파악해야한다.

 

이후 정보를 바탕으로 치즈와 맞닿아있는 공기가 치즈 외부에 있는 공기이고 갯수가 2개 이상이라면 치즈를 녹여주면 된다.

 

이후의 부분은 방문 체크만 잘해주면 구현 조건이 까다로운 편은 아니기 때문에 크게 어려운 부분은 없는 것 같다

 

전체적인 로직을 차례대로 나열해 본다면

1. 공기가 치즈 외부의 공기인지 치즈 내부의 공기인지 확인한다.(치즈 내부의, 외부와 맞닿아 있지 않는 공기이면 치즈를 녹이는데 영향X) - 가장자리부터 BFS

2. 각각의 치즈에서 4방향을 탐색하여 치즈 외부의 공기이며 갯수가 2개 이상인지 확인

3. 치즈가 다 사라질 때까지 반복

---

2. Code

#include <bits/stdc++.h>

using namespace std;

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

vector<vector<int>> cheese(101, vector<int>(101, 0));
bool vis[101][101];
bool meltCnt[101][101];
bool isAir[101][101]; //외부공기인지 체크

// 치즈 외부에서 BFS를 돌면서 확인
void isInsideAir() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    vis[0][0] = true;
    isAir[0][0] = true;

    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;

        q.pop();

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

            if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if(cheese[ny][nx] == 1) continue;
            if(vis[ny][nx]) continue;
            q.push({ny, nx});
            vis[ny][nx] = true;
            isAir[ny][nx] = true;
        }
    }
}

void BFS(int yy, int xx) {
    queue<pair<int, int>> q;

    q.push({yy, xx});
    vis[yy][xx] = true;

    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        int airCnt = 0;

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(cheese[ny][nx] == 0 && isAir[ny][nx]) 
                airCnt++;
            if(cheese[ny][nx] == 1 && !vis[ny][nx]) {
                q.push({ny, nx});
                vis[ny][nx] = true;
            }
        }
        if(airCnt >= 2) {
            //airCnt가 2이상이면 이후에 치즈 녹이기
            meltCnt[y][x] = true;
        }
    }
}

//치즈 녹이기
void melt() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(meltCnt[i][j]) {
                cheese[i][j]--;
                meltCnt[i][j] = false;
            }
            vis[i][j] = false;
            isAir[i][j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(meltCnt, false, sizeof(meltCnt));
    
    cin >> n >> m;

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

    int answer = 0;

    while (true) {
        //공기가 치즈 내부의 공기인지 외부의 공기인지 확인
        isInsideAir();
        memset(vis, false, sizeof(vis));
        bool cheeseCheck = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(cheese[i][j] == 1 && !vis[i][j]) {
                    BFS(i, j);
                    cheeseCheck = true;
                }
            }
        }
        //치즈를 한번도 한번도 안녹이면 루프빠지기
        if(!cheeseCheck) break;
        else melt();
        answer++;
    }
    cout << answer;
}

 

 

---

3. Feedback

치즈 내부의 공기를 어떻게 걸러낼지 생각을 떠올리는데 시간이 좀 오래 걸린 것 같다. 그래도 20분 이내로 생각해내서 엄청나게 길게 생각한 것은 아니라 그동안 알고리즘 공부를 하면서 조금은 성장했다고 느낄 수 있었다! 

답지를 보지 않고 풀은 문제중에서 티어가 높은 문제여서 기분이 좋다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐