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

백준의 치즈(2638) 문제이다.

[ 문제 바로가기 ]

( 치즈(2636)과 비슷한 부분이 있으니, 먼저 치즈(2636)의 풀어보시고 풀이를 읽고 오는 것을 권장합니다.

  [ 치즈(2636)풀이 바로가기 ])

[ 문제풀이 ]

1) 치즈(2636) 문제에서 조금 변형된 문제이다.
   치즈(2636) 문제에서는 치즈 주변에 있는 공기를 기준 삼아서 진행했다면 이 문제에서는 치즈를 기준 삼아서

   접근해 보았다.

   전체적인 틀은 치즈(2636)과 비슷하다.

   먼저, 구체적인 구현 과정을 들어가기 전에 본인은 입력과 동시에 치즈들의 좌표를 vector를 하나 선언해서 모두 저장해

   주었다.

   vector에서는 3개의 자료를 관리하도록 만들어 주었다. 해당 치즈의 x좌표 , y좌표 그리고 해당 치즈가 녹았는지

   아직 안녹았는지를 판단하는 bool형 자료 이렇게 총 3개를 관리해 주었다.

   당연히 초기 상태에서는 모든 치즈가 녹지 않은 상태이기 때문에 vector에는 각 치즈들의 좌표 , 'false'로 저장되어 있을

   것이다.

   본인이 구현한 내용을 순서대로 적어보자면 다음과 같다.

   1. 치즈 외부에 있는 공기와 내부에 있는 공기 나누기

   2. 녹을 수 있는 치즈 찾기

   3. 실제로 치즈를 녹이기

   4. 치즈가 녹음으로써 기존에 치즈 내부에 있던 공기였지만 외부와 연결될 수 있는 공기들이 존재할 수 있으므로

     그런 공기들을 합쳐주기

   5. 모든 치즈가 녹을 때 까지 2 ~4의 과정을 반복.

   그럼 각 과정들에 대해서 구체적으로 알아보자.

   1. 치즈 외부에 있는 공기와 내부에 있는 공기 나누기

   - 이 과정은 2번을 위해서 필요한 과정이다. 치즈는 최소 2변 이상이 공기와 맞닿아 있으면 녹게 된다.

     하지만, 단순히 치즈를 기준으로 상하좌우를 탐색했을 때, MAP의 값이 0이라면 공기와 맞닿아 있다고 판단하면

     안된다. 왜냐하면 그 공기가 치즈 내부에 있는 공기라서 치즈를 녹일 수 없는 공기라면, 이는 치즈와 맞닿은

     공기라고 계산하면 안되기 때문이다.

     그래서 본인은 공기를 나누기 위해서 int Visit[][] 라는 2차원 배열을 하나 만들어 주어서 표시해 주었다.

     입력과 동시에 치즈가 있는 좌표의 Visit값들을 -1로 바꿔주었고, 이 1번과정에서는 (0, 0)에서부터 BFS탐색을

     진행해서 연결되어 있는 모든 공기들의 Visit값을 1로 바꿔주었다.

     그렇게 되면 내부에 치즈들은 연결되어 있지 않기 때문에 당연히 Visit의 값이 0으로 남아 있을 것이다.

   2. 녹을 수 있는 치즈 찾기

   - 위에서도 말했듯이, 본인은 입력과 동시에 치즈가 존재하는 좌표를 vector에 넣어주었다.

     이 vector의 원소들을 하나하나 반복하면서, 2변 이상의 공기와 맞닿은 치즈들만 또 다른 벡터

     (본문 : vector<pair<int,int>> Cheese) 에 저장해주었다.

     또한, 이 Cheese에 들어갈 조건을 만족하는 치즈들의 경우, 기존에 모든 치즈의 좌표를 저장해 놓은 벡터에서

     녹았는지를 판단하는 bool형 변수를 모두 true로 바꿔주었다.

     왜냐하면, 아직 실질적으로 녹지는 않았지만 이 놈들은 이번 턴에 녹을 치즈들이기 때문에 바꿔주었다.

   3. 실제로 치즈를 녹이기

   - 2번에서 저장해 놓은 '녹을 수 있는 치즈들'의 좌표를 모두 0으로 바꿔주었다.

     또한, 치즈(2636)문제에서 했듯이, 전역변수로 Queue를 하나 선언해서, 해당 Queue에 이 좌표들을 넣어주었다.

     왜냐하면 지금 녹는 치즈들은, 공기가 될 것이고, 이 공기에 의해서 기존에 치즈 내부에 존재했던 공기들과

     연결될 수 있기 때문이다.

    

     이런 경우를 생각해보자.

     위에서 빨간색으로 표시해놓은 치즈들은, 2번 과정(녹을 수 있는 치즈를 찾아서 벡터에 저장하는 과정)

     에서 벡터에 삽입될 좌표들이다. 동시에, 저 치즈들은 녹으면서 내부 공기와 외부공기를 연결시켜 줄 수 있는

     좌표들이다. 그래서, 이 좌표들을 '녹았습니다'라는 표시로 MAP에서 0으로 바꿔줌과 동시에

     전역변수로 선언해 놓은 Queue에 좌표를 저장해 주었다. 이 Queue는 4번과정에서 사용된다.

    4. 외부공기와 내부공기를 연결시켜주기

    - 이 과정을 위해서 Queue에 위에서 말한 좌표들을 저장해 준 것이다. 사실, 이렇게 하지 않고 치즈를 한번

      녹일 때 마다, (0, 0)에서 부터 BFS탐색을 진행해서 외부에 있는 공기를 판단해줘도 상관은 없지만, 시간이 보다

      오래 걸리게 된다.

      물론, 시간이 오래걸려서 pass를 받지 못하거나 그러지는 않는다. 본인이 2가지 방법으로 모두 해봤는데 2가지 방법

      모두 pass를 받을 수는 있다.

      하지만, 저 좌표들에서만 BFS탐색을 진행한다면 시간을 줄일 수 있을 것이다.

      탐색 조건은 '탐색하려는 좌표의 Visit의 값이 0이라면, 1로 바꿔주고 탐색 진행' 이다.

      이렇게 되면, 원래는 내부에 있는 공기라서 Visit의 값이 0였지만, 외부와 합쳐지면서 외부 공기를 의미하도록 Visit의

      값 또한 1로 바뀌게 될 것이다.

  

 [ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<pair<int, int>, bool>> V;    // 치즈의 좌표를 저장하는 Vector.
vector<pair<int, int>> Cheese;            // 현 시점에서, 녹을 수 있는 치즈만 저장하는 Vector.
queue<pair<int, int>> NQ;                // 외부공기와 내부공기를 합치기 위한 과정에서 사용하는 Queue
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1)
            {
                V.push_back(make_pair(make_pair(i, j), false));
                Visit[i][j] = -1;
            }
        }
    }
}
 
void Divide_Air()
{
    /* 외부공기와 내부공기 나누기. */
    /* 맵의 테두리에는 치즈가 놓여있지 않으므로, 
     * (0, 0)에서 탐색을 진행하면서 연결되어 있는 공기들만 탐색.
     */
    queue<pair<int, int>> Q;
    Q.push(make_pair(0, 0));
    Visit[0][0] = 1;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        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 < N && ny < M)
            {
                if (Visit[nx][ny] == 0) 
                {
                    Visit[nx][ny] = 1;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Find_Cheese_List()
{
    /* 실질적으로 녹는 치즈들만 저장하는 과정. */
    Cheese.clear();
    for (int i = 0; i < V.size(); i++)
    {
        if (V[i].second == true) continue;
        // 이미 녹은 치즈에 대해서는 탐색할 필요 없음.
 
        int x = V[i].first.first;
        int y = V[i].first.second;
        int Cnt = 0;
 
        for (int j = 0; j < 4; j++)
        {
            int nx = x + dx[j];
            int ny = y + dy[j];
            if (MAP[nx][ny] == 0 && Visit[nx][ny] == 1) Cnt++;
            // 단순히, MAP[nx][ny] == 0이 아닌, Visit의 값으로 외부공기인지 내부공기인지
            // 체크도 해줘야 한다.
        }
 
        if (Cnt >= 2)
        {
            Cheese.push_back(make_pair(x, y));
            V[i].second = true;
        }
    }
}
 
void Melting_Cheese()
{
    /* 치즈를 실제로 녹이는 과정.*/
    /* 동시에, 외부공기 + 내부공기를 위해 사용될 Queue에 좌표 저장하기. */
    for (int i = 0; i < Cheese.size(); i++)
    {
        int x = Cheese[i].first;
        int y = Cheese[i].second;
        MAP[x][y] = 0;
        NQ.push(make_pair(x, y));
    }
}
 
void Add_Air()
{
    /* 외부공기와 내부공기를 합쳐주는 과정. */
    while (NQ.empty() == 0)
    {
        int x = NQ.front().first;
        int y = NQ.front().second;
        NQ.pop();
 
        Visit[x][y] = 1;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (Visit[nx][ny] == 0)
            {
                Visit[nx][ny] = 1;
                NQ.push(make_pair(nx, ny));
            }
        }
    }
}
 
bool Clear()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (MAP[i][j] == 1) return false;
        }
    }
    return true;
}
 
void Solution()
{
    Divide_Air();
    int Time = 0;
    while (1)
    {
        if (Clear() == true) break;
        Find_Cheese_List();
        Melting_Cheese();
        Add_Air();
        Time++;
    }
 
    cout << Time << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}