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

🔗문제 보러가기

2636번: 치즈

 

👨‍💻풀이 과정

 

구현 문제는 요구 사항이 많기 때문에, 구현해야 할 기능별로 함수화하여 접근하는 게 가장 좋은 것 같습니다. 이 문제에서 구현해야 할 요구사항들은 다음과 같습니다.

---

1. 문제에서 주어진 입력을 받는 함수 

 

문제에서 가로 행의 개수와 세로 행의 개수, 그리고 판의 상태를 입력으로 줍니다. 이러한 내용들을 배열에 입력받되, 치즈의 개수 또한 세서 별도의 변수에 저장해주었습니다. 이 치즈의 개수가 루프 종료 조건이기 때문이죠.

 

2. 공기를 주변으로 확산시키는 함수

 

해당 문제의 초기 빈 정사각형은 치즈의 바깥에 있다면 공기를, 치즈의 내부에 있다면 진공 상태를 의미합니다. 또한, 공기와 접촉한 치즈가 녹아 내부 진공 공간이 외부로 노출되면, 공기가 안에 흘러들어가야 하므로 이러한 역할을 하는 함수가 필요하겠습니다.

 

3. 공기에 노출된 치즈를 찾는 함수

 

이 문제에서 구현해야 할 핵심 기능입니다. 2중 for 문으로 전체 맵을 순회하다가 치즈를 발견하면, 해당 치즈의 상하좌우 인접 칸을 조사하여 공기가 있는지를 검사합니다. 만약 공기가 있다면, 해당 치즈는 한 시간 뒤에 녹아내릴 치즈이므로 제거 대상 리스트에 올려주면 됩니다.

 

4. 공기에 노출된 치즈를 제거하는 함수

 

3번 함수에서 찾은 치즈들을 제거해주면 되지만, 중요한 점은 제거한 치즈가 내부 진공 공간의 벽 역할을 하던 치즈일 수도 있다는 부분입니다. 이 때에는 공기가 내부 진공 공간으로 유입되어야 하므로, 치즈를 제거한 후 2번 함수를 통해 공기 확산을 시켜줍니다.

---

 

이러한 함수들을 조합하여 치즈가 다 제거될 때까지 3, 4번 함수를 돌리면 됩니다. 그 과정에서 루프를 한 번 돌 때마다 시간을 +1 해주고, 제거하기 전의 치즈 개수 또한 별도로 저장해주면 되겠습니다.

 

 

✏️소스 코드 및 결과

#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 AIR -1
#define VACUUM 0
#define CHEESE 1
#define AIR_EXPOSED_CHEESE 2

int MaxRow, MaxColumn, NumOfCheeses;
vector<vector<int>> Field;
vector<Point> Directions { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue<Point> AirExposedCheeses;

void Initialize()
{
    cin >> MaxRow >> MaxColumn;
    Field.resize(MaxRow, vector<int>(MaxColumn));

    for (int r = 0; r < MaxRow; r++)
    {
        for (int c = 0; c < MaxColumn; c++)
        {
            cin >> Field[r][c];
            if (Field[r][c] == CHEESE) NumOfCheeses++;
        }
    }
}

void SetExternalAir(int row, int column)
{
    queue<Point> externalAirs;
    Field[row][column] = AIR;
    externalAirs.push(Point(row, column));

    while (!externalAirs.empty())
    {
        row = externalAirs.front().first;
        column = externalAirs.front().second;
        externalAirs.pop();

        for (const Point& direction : Directions)
        {
            int nextRow = row + direction.first;
            int nextColumn = column + direction.second;

            if (nextRow < 0 or nextRow >= MaxRow or nextColumn < 0 or nextColumn >= MaxColumn)
                continue;
            if (Field[nextRow][nextColumn] == CHEESE or Field[nextRow][nextColumn] == AIR)
                continue;
            
            Field[nextRow][nextColumn] = AIR;
            externalAirs.push(Point(nextRow, nextColumn));
        }
    }
}

bool IsAirExposedCheese(int row, int column)
{
    for (const Point& direction : Directions)
    {
        int nextRow = row + direction.first;
        int nextColumn = column + direction.second;

        if (Field[nextRow][nextColumn] == AIR)
            return true;
    }

    return false;
}

void FindAirExposedCheeses()
{
    for (int r = 0; r < MaxRow; r++)
    {
        for (int c = 0; c < MaxColumn; c++)
        {
            if (Field[r][c] == AIR or Field[r][c] == VACUUM or Field[r][c] == AIR_EXPOSED_CHEESE)
                continue;

            if (IsAirExposedCheese(r, c))
            {
                Field[r][c] = AIR_EXPOSED_CHEESE;
                AirExposedCheeses.push(Point(r, c));
            }
        }
    }
}

int RemoveAirExposedCheeses()
{
    int count = AirExposedCheeses.size();

    for (int i = 0; i < count; i++)
    {
        Point position = AirExposedCheeses.front();
        AirExposedCheeses.pop();
        SetExternalAir(position.first, position.second);
    }

    return count;
}

int main()
{
    FAST_IO
    Initialize();
    SetExternalAir(0, 0);

    int numOfCheesesAnHourAgo = NumOfCheeses;
    int currentNumOfCheeses = NumOfCheeses;
    int hour = 0;
    
    while (currentNumOfCheeses > 0)
    {
        FindAirExposedCheeses();
        numOfCheesesAnHourAgo = currentNumOfCheeses;
        currentNumOfCheeses -= RemoveAirExposedCheeses();
        hour++;
    }

    cout << hour << "\n" << numOfCheesesAnHourAgo;
    return 0;
}