[백준 2638] 치즈

🔗 알고리즘 문제

이제 그래프 탐색 마스터를 해버린건지, 골드 3이지만 쉽다? 라고 느껴진 문제. 문제를 보자마자 생각난 방법으로 코드를 짜고 바로 정답을 받아 너무 행복했던 문제이다.

문제 분석

문제가 조금 길지만, 정리해보자면 2차원 배열에서 1이 모두 없어질 때 까지 몇번 걸리는지를 알아내는 문제이다.

배열에서 1이 없어지는 기준은 다음과 같다.

칸의 4변 중 2변 이상이 0과 닿아있어야 한다.
단, 1로 둘러싸인 공간안에 있는 0은 영향을 주지 못한다.

발상 & 알고리즘 설계

이 문제에서 중요하게 봐야 하는 부분은 내부 0 공간과 외부 0 공간을 구분하는 것. 그리고 2변 이상이 맞닿아 있다는 것을 구분하는 것 이렇게 두가지 이다.

우선 내부 0 공간과 외부 0 공간은 모순적이지만 굳이 구분할 필요가 없다. 왜냐하면 배열에 0, 0자리에는 절대 1이 올 수 없고, 0, 0을 시작점으로 BFS를 진행하면 내부 0 공간을 탐색이 불가하기에 모든 1이 없어질 때 까지 0, 0을 시작점으로 BFS를 진행한다면 굳이 내부와 외부를 구분하지 않아도 된다.

2변 이상이 맞닿아 있다는 것을 확인하기 위해 기존 check 방식을 방문했냐 안했냐가 아닌 몇 번 방문했냐? 를 담아주도록 하였다. 이렇게 하면 BFS가 진행 된 후 check 배열 속 값이 2이상이라면 그것은 0과 2번 이상 맞닿아있다는 뜻이된다.

위와 같은 규칙을 지키며 1의 갯수가 0이 될 때 까지 BFS를 진행하여 문제를 해결하였다.

코드

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int destX[4] = { -1, 1, 0, 0 };
int destY[4] = { 0, 0, -1, 1 };

int board[101][101] = {};
int check[101][101] = {};

int n;
int m;

int target = 0;
int answer = 0;

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

    q.emplace(0, 0);
    check[0][0] = 1;

    while(!q.empty()){
        pair<int, int> node = q.front();
        q.pop();

        for(int i = 0; i < 4; i++){
            pair<int, int> next = { node.first + destX[i], node.second + destY[i] };

            if(next.first < 0 || next.first > m - 1 || next.second < 0 || next.second > n - 1)
                continue;

            if(board[next.second][next.first] == 1){
                check[next.second][next.first]++;
                continue;
            }

            if(check[next.second][next.first] == 1)
                continue;

            check[next.second][next.first] = 1;
            q.push(next);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;

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

    while(target != 0){
        memset(check, 0, sizeof(check));

        BFS();

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(check[i][j] >= 2){
                    --target;
                    board[i][j] = 0;
                }
            }
        }

        ++answer;
    }

    cout << answer;
}