[C++] 백준 온라인 저지 2638번 치즈 풀이

치즈가 다 녹는 데 몇 시간 걸리는 지 구하는 문제

 

---

문제

 

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

 

<그림 1>

 

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

 

<그림 2>

 

<그림 3>

 

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

 

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

 

 

풀이



처음에 생각한 풀이 과정

1. 입력 받은 후 맵을 BFS 탐색해서 치즈 내부 공기를 구분해서 표시해 준다. 이 과정에서 치즈 위치만 따로 벡터에 저장한다. 

 

2. 치즈 위치를 저장한 벡터를 탐색하면서 녹을 치즈라면 녹을 치즈 위치를 저장한 벡터에 저장한 후 치즈 위치를 저장한 벡터에서 삭제한다. 

 

3. 녹을 치즈 위치를 저장한 벡터를 순회하면서 치즈를 녹인다. 

 

4. 맵을 BFS 탐색하면서 내부 공기가 외부 공기와 닿은 곳은 외부 공기로 바꿔준다. 

 

5. 시간을 증가시킨다. 

 

6. 이것을 치즈 위치를 저장한 벡터의 사이즈가 0이 될 때까지 반복한다. 

 

 하지만 결과는... 시간 초과에다 최적화를 해도 9%에서 틀림 ㅠ.ㅠ 그래서 

 

https://yabmoons.tistory.com/342

[ 백준 2638 ] 치즈 (C++)

 이 블로그를 참고해서 풀었습니다. 

 

수정한 풀이

1. 외부 공기 0/ 치즈 1/ 내부 공기 2 로 define 값 선언

 

2. 입력으로 주어지는 치즈 맵을 저장할 2차원 벡터 Map과 외부 공기와 내부 공기의 위치를 저장할 2차원 벡터 airArea를 만든다. 

 

3. 입력 받으면서 현재 위치의 입력이 0(공기)라면 airArea의 현재 위치 값을 2(내부공기)로 저장한다. 1(치즈)라면 치즈 위치를 저장할 벡터 cheese에 위치(pair<pair<int, int>, bool> 형태, bool 초기값은 false)를 저장한다. 

 

4. BFS로 0,0부터 탐색하면서 치즈 바깥에 있는 곳이라면 0(외부 공기)으로 바꿔준다. 이 과정을 거치면 치즈 바깥에 있는 공기들은 모두 0이 되어 있고 치즈 내부의 빈 공간은 2로 남아 있을 것이다. 

 

5. cheese를 처음부터 탐색하면서 bool 값이 false라면 치즈가 녹지 않았다는 것임. false인데 2면 이상 외부 공기와 닿아서 곧 녹을 치즈라면 녹을 치즈 위치를 저장할 벡터 willBeMelt에 저장한다. 

 

6. willBeMelt를 순회하면서 치즈들을 녹인다. 이 때 치즈가 녹으면서 내부 공기가 외부 공기와 닿았다면 내부 공기를 외부 공기로 바꿔줘야 하니까 치즈를 녹인 위치 주변을 탐색할 필요가 있다. 내부 공기 탐색을 위해 내부 공기 위치를 저장할 큐 airQueue를 만들어서 이 큐에 녹은 치즈 위치를 저장한다. 

 

7. airQueue를 BFS로 탐색하면서 내부 공기가 외부 공기와 닿았으면 외부 공기로 바꿔준다. 

 

8. 정답을 증가시킨다. 

 

9. 위 과정이 끝나면 모든 치즈가 녹았는지 검사한다. 모든 치즈가 녹았으면 정답을 출력하고 아니라면 다시 반복한다. 

 

 

코드

 

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

using namespace std;

const int AIR = 0;
const int CHEESE = 1;
const int INSIDE = 2; //가독성 향상을 위한 define 값

vector<vector<int>> dir; //확인할 방향
vector<vector<int>> airArea; //공기 종류 구분용
vector<vector<int>> Map; //입력으로 주어지는 치즈 맵

vector<pair<pair<int, int>, bool>> cheese; //치즈 위치
vector<pair<int, int>> willBeMelt; //녹을 치즈 위치

queue<pair<int, int>> airQueue; //내부 공기 위치

void checkCheese()
{
    willBeMelt.clear();
    for (int i = 0; cheese.size() > i; i++)
    {
        //true라면 이미 녹은 치즈니까 넘어감
        if (cheese[i].second)
            continue;
        
        //아직 녹지 않았으면
        auto cur = cheese[i].first;
        int airCount = 0;
        for (int j = 0; dir.size() > j; j++)
        {
            auto next = make_pair(cur.first + dir[j][0], cur.second + dir[j][1]);
            //치즈 맵에서 외부 공기와 닿아 있는데 공기 맵에서도 외부 공기와 닿아 있으면 카운트 증가
            if (AIR == Map[next.first][next.second] && AIR == airArea[next.first][next.second])
                airCount++;
        }
        
        //2면 이상 닿아 있으면 곧 녹을 치즈
        if (2 <= airCount)
        {
            willBeMelt.emplace_back(cur);
            cheese[i].second = true;
        }
    }
}

void meltCheese()
{
    for (int i = 0; willBeMelt.size() > i; i++)
    {
        auto cur = willBeMelt[i];
        Map[cur.first][cur.second] = AIR;
        //치즈가 녹은 후 주변을 탐색해서 내부 공기를 외부 공기로 바꿔줘야 하니까 큐에 위치 저장
        airQueue.emplace(cur);
    }
}

void blendAir()
{
    while (!airQueue.empty())
    {
        auto cur = airQueue.front();
        airQueue.pop();
        
        airArea[cur.first][cur.second] = AIR;
        for (int i = 0; dir.size() > i; i++)
        {
            auto next = make_pair(cur.first + dir[i][0], cur.second + dir[i][1]);
            if (INSIDE == airArea[next.first][next.second])
            {
                //내부 공기가 외부 공기와 닿았다면 외부 공기로 바꿔준다.
                airArea[next.first][next.second] = AIR;
                airQueue.emplace(next);
            }
        }
    }
}

void divideAir()
{
    //치즈 바깥에 있는 내부 공기값들은 외부 공기값으로 바꿔준다.
    queue<pair<int, int>> q;
    q.emplace(make_pair(0, 0));
    
    airArea[0][0] = AIR;
    
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();
        
        for (int i = 0; dir.size() > i; i++)
        {
            auto next = make_pair(cur.first + dir[i][0], cur.second + dir[i][1]);
            if (0 > next.first || airArea.size() <= next.first ||
                0 > next.second || airArea[0].size() <= next.second)
                continue;
            if (INSIDE == airArea[next.first][next.second])
            {
                airArea[next.first][next.second] = AIR;
                q.emplace(next);
            }
        }
    }
}

bool allMelt()
{
    //모든 치즈가 녹았는지 확인
    for (int i = 0; Map.size() > i; i++)
    {
        for (int j = 0; Map[i].size() > j; j++)
        {
            if (CHEESE == Map[i][j])
                return false;
        }
    }
    
    return true;
}

int main()
{
    dir.push_back({0,1});
    dir.push_back({0,-1});
    dir.push_back({-1,0});
    dir.push_back({1,0});
    
    int height, width;
    cin >> height >> width;
    
    Map.assign(height, vector<int>(width, 0));
    airArea.assign(height, vector<int>(width, 0));
    for (int i = 0; height > i; i++)
    {
        for (int j = 0; width > j; j++)
        {
            cin >> Map[i][j];
            
            if (CHEESE == Map[i][j])
            {
                //치즈라면 치즈 위치를 따로 저장하고
                cheese.emplace_back(make_pair(i, j), false);
                //공기 맵에서도 치즈로 세팅
                airArea[i][j] = CHEESE;
            }
            //공기 맵에서 내부 공기로 세팅
            else
                airArea[i][j] = INSIDE;
        }
    }
    
    divideAir();
    
    int answer = 0;
    while (true)
    {
        if (allMelt())
            break;
        
        checkCheese();
        meltCheese();
        blendAir();
        answer++; //시간 증가
    }
    
    cout << answer;
    
    return 0;
}