[BOJ] 2638번 | 치즈 (C++)

🔗문제 보러가기

2638번: 치즈

 

👨‍💻풀이 과정

 

내부 공기와 외부 공기를 어떻게 구별할까 고민했습니다. 문득 떠오른 생각은 다각형 외부 내부 판별 알고리즘이었는데, 치즈가 다각형이 아닐 수도 있기 때문에 적용할 수가 없더라구요.

 

그래서 문제에서 주어진 정보인, "가장자리에는 치즈가 놓이지 않는다"라는 걸 활용해 가장자리에서부터 BFS를 통해 외부 공기를 만들어주기로 결정하였습니다. 이 로직을 위해, 입력 세팅을 할 때 조금 다르게 세팅해주었습니다.

// 전역 변수들
#define EXTERNAL_AIR -1
#define AIR -2
#define REMOVE_TARGET_CHEESE -3

using Point = pair<int, int>;
int MaxRow, MaxCol;
vector<vector<int>> Directions{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void Initialize(vector<vector<int>>& field)
{
    for (int row = 0; row < MaxRow; row++)
    {
        for (int col = 0; col < MaxCol; col++)
        {
            cin >> field[row][col];

            if (field[row][col] == 0)       field[row][col] = AIR;
            else if (field[row][col] == 1)  field[row][col] = 0;        // 치즈가 외부 공기와 접촉하는 칸 수 (우선 초깃값은 모두 0으로)
        }
    }
}

 

기존 입력에서 공기였던 칸(0)을 AIR(-2)로, 치즈였던 칸(1)을 0으로 세팅해주었습니다. 이는 치즈가 있는 칸의 정보를 외부 공기가 접촉하는 변의 수로 설정해주기 위함입니다. 내부 깊숙히 있는 치즈의 경우에는 외부 공기와 접촉하지 않아 0이란 값을 갖기 때문에, 공기와 이를 구별해주기 위해 다르게 세팅하였습니다.

 

 

그 후, 가장자리에는 치즈가 없기 때문에 (0, 0) 위치에서부터 BFS 방식을 통해 외부 공기를 세팅해주었습니다.

그 과정에서 치즈를 만나게 되면, 해당 치즈의 값을 1 증가시켜주었습니다.

만약 해당 치즈의 값이 2 이상이라면, 제거할 대상으로 간주하고 별도의 큐(Queue)에 담아주었습니다.

void FillExternalAirAndFindRemovingCheeses(vector<vector<int>>& field, queue<Point>& removeTargetCheeses, int startRow, int startCol)
{
    queue<Point> positions;
    field[startRow][startCol] = EXTERNAL_AIR;
    positions.emplace(Point(startRow, startCol));

    while (!positions.empty())
    {
        int row = positions.front().first;
        int col = positions.front().second;
        positions.pop();

        for (const vector<int>& direction : Directions)
        {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (nextRow < 0 or nextRow >= MaxRow or nextCol < 0 or nextCol >= MaxCol)
                continue;

            if (field[nextRow][nextCol] == EXTERNAL_AIR or field[nextRow][nextCol] == REMOVE_TARGET_CHEESE)
                continue;
            
            if (field[nextRow][nextCol] >= 0)   // 치즈일 경우, 외부 접촉 공기 개수를 늘려주기
            {
                field[nextRow][nextCol]++;

                if (field[nextRow][nextCol] >= 2)
                {
                    field[nextRow][nextCol] = REMOVE_TARGET_CHEESE;
                    removeTargetCheeses.emplace(Point(nextRow, nextCol));
                }
                continue;
            }

            field[nextRow][nextCol] = EXTERNAL_AIR;
            positions.emplace(Point(nextRow, nextCol));
        }
    }
}

 

이렇게 외부 공기를 채우고 제거할 치즈들을 찾았다면, 치즈를 제거하고 제거한 자리에서 다시 외부 공기를 퍼트리고, 그 과정에서 또 제거할 치즈를 찾고... 이 과정을 더 이상 제거할 치즈가 없을 때까지 반복해줍니다.

void Update(vector<vector<int>>& field, queue<Point>& removeTargetCheeses)
{
    int size = removeTargetCheeses.size();

    for (int i = 0; i < size; i++)
    {
        Point cheesePosition = removeTargetCheeses.front();
        int row = cheesePosition.first;
        int col = cheesePosition.second;

        removeTargetCheeses.pop();
        FillExternalAirAndFindRemovingCheeses(field, removeTargetCheeses, row, col);
    }
}

 

위의 함수들을 main() 함수에서 잘 동작하도록 실행해주면 끝입니다.

int main()
{
    FAST_IO
    cin >> MaxRow >> MaxCol;

    // 1. 입력 받고 세팅
    vector<vector<int>> field(MaxRow, vector<int>(MaxCol));
    Initialize(field);

    // 2. 외부 공기를 채우고, 그 과정에서 제거할 치즈들 찾기
    queue<Point> removeTargetCheeses;
    FillExternalAirAndFindRemovingCheeses(field, removeTargetCheeses, 0, 0);   // 가장자리에는 치즈가 없다고 했으므로 (0, 0)부터 시작

    // 3. 더 이상 제거할 치즈가 없을 때까지 반복
    int time = 0;
    while (!removeTargetCheeses.empty())
    {
        Update(field, removeTargetCheeses);
        time++;
    }

    cout << time;
    return 0;
}

 

 

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
using Point = pair<int, int>;

#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define EXTERNAL_AIR -1
#define AIR -2
#define REMOVE_TARGET_CHEESE -3


int MaxRow, MaxCol;
vector<vector<int>> Directions{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void FillExternalAirAndFindRemovingCheeses(vector<vector<int>>& field, queue<Point>& removeTargetCheeses, int startRow, int startCol)
{
    queue<Point> positions;
    field[startRow][startCol] = EXTERNAL_AIR;
    positions.emplace(Point(startRow, startCol));

    while (!positions.empty())
    {
        int row = positions.front().first;
        int col = positions.front().second;
        positions.pop();

        for (const vector<int>& direction : Directions)
        {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (nextRow < 0 or nextRow >= MaxRow or nextCol < 0 or nextCol >= MaxCol)
                continue;

            if (field[nextRow][nextCol] == EXTERNAL_AIR or field[nextRow][nextCol] == REMOVE_TARGET_CHEESE)
                continue;
            
            if (field[nextRow][nextCol] >= 0)   // 치즈일 경우, 외부 접촉 공기 개수를 늘려주기
            {
                field[nextRow][nextCol]++;

                if (field[nextRow][nextCol] >= 2)
                {
                    field[nextRow][nextCol] = REMOVE_TARGET_CHEESE;
                    removeTargetCheeses.emplace(Point(nextRow, nextCol));
                }
                continue;
            }

            field[nextRow][nextCol] = EXTERNAL_AIR;
            positions.emplace(Point(nextRow, nextCol));
        }
    }
}

void Update(vector<vector<int>>& field, queue<Point>& removeTargetCheeses)
{
    int size = removeTargetCheeses.size();

    for (int i = 0; i < size; i++)
    {
        Point cheesePosition = removeTargetCheeses.front();
        int row = cheesePosition.first;
        int col = cheesePosition.second;

        removeTargetCheeses.pop();
        FillExternalAirAndFindRemovingCheeses(field, removeTargetCheeses, row, col);
    }
}

void Initialize(vector<vector<int>>& field)
{
    for (int row = 0; row < MaxRow; row++)
    {
        for (int col = 0; col < MaxCol; col++)
        {
            cin >> field[row][col];

            if (field[row][col] == 0)       field[row][col] = AIR;
            else if (field[row][col] == 1)  field[row][col] = 0;        // 치즈가 외부 공기와 접촉하는 칸 수 (우선 초깃값은 모두 0으로)
        }
    }
}

int main()
{
    FAST_IO
    cin >> MaxRow >> MaxCol;

    // 1. 입력 받고 세팅
    vector<vector<int>> field(MaxRow, vector<int>(MaxCol));
    Initialize(field);

    // 2. 외부 공기를 채우고, 그 과정에서 제거할 치즈들 찾기
    queue<Point> removeTargetCheeses;
    FillExternalAirAndFindRemovingCheeses(field, removeTargetCheeses, 0, 0);   // 가장자리에는 치즈가 없다고 했으므로 (0, 0)부터 시작

    // 3. 더 이상 제거할 치즈가 없을 때까지 반복
    int time = 0;
    while (!removeTargetCheeses.empty())
    {
        Update(field, removeTargetCheeses);
        time++;
    }

    cout << time;
    return 0;
}