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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본인이 풀이한 과정을 차근차근 순차적으로 알아보자.

   본인은 가장 먼저, 맵의 초기상태에서 공기들 중에서 치즈 외부에 있는 공기와 치즈 내부에 있는 공기를 나눠주었다.

   나눠준 이유는 간단하다. 내부에 있는 이유는 치즈에 어떠한 영향력도 미치지 못하지만, 외부에 있는 공기는 치즈를

   녹일 수 있기 때문이다.

   외부와 내부의 공기를 구분하기 위해서 int Visit[][] 라는 2차원 int형 배열을 선언해 주었다.

   초기에 치즈가 있는 좌표의 Visit값은 -1로 초기화 시켜주었고, 그게 아닌 공기가 있는 곳들에는 0으로 초기화를

   시켜주었다.

   이 후, (0, 0)에서부터 너비우선탐색(BFS)을 진행함으로써 연결되어 있는 모든 공기 좌표들의 Visit 값을 1로 초기화

   시켜주었다.

   BFS탐색 한번 만으로도 이렇게 값을 바꿀 수 있는 이유는, BFS의 탐색 조건이

   "움직이려는 좌표가 공기이고, 아직 방문하지 않았다면" 이기 때문이다. 분명, 외부에 있는 공기들을 모두 연결되어

   있을 것이다. 왜냐하면 문제에서 "맵의 가장자리에는 젇래로 치즈가 놓여져 있지 않다" 라고 했기 때문에

   (0, 0)에서 탐색을 시작해서 너비우선탐색을 진행하고, 진행하면서 외부에 있는 공기들의 Visit값을 1로 체크해 주면

   외부에 있는 공기들만 Visit의 값이 1이 되어있을 것이고, 치즈 내부에 있는 공기들은 당연히 치즈 때문에 외부와

   연결되어 있지 않으므로 Visit값이 0으로 남아 있을 것이다.

   이렇게 가장 먼저 치즈 내부와 외부의 공기를 나눠주었다.

   두번째는 외부에 존재하는 공기들 중에서도, 치즈와 인접한 공기들만 따로 저장해 주었다.

   이 부분을 위해 전역변수로 Queue를 하나 선언해 주었다. Queue를 굳이 왜 전역변수로 선언했는지는

   차근차근 알아보자. 지금부터 이 전역변수로 선언된 Queue의 이름을 'NQ'라고 하겠다.(Next_Queue의 줄인 말)

   외부에 있는 공기들을 하나한 다 탐색하면서(Visit = 1로 설정되어 있는 좌표들을 다 탐색하면서)

   인접한 4방향에 치즈가 있는 좌표들을 NQ에 넣어주었다.

   이렇게되면, 외부에 존재하는 공기들 중에서도, 치즈와 인접한 공기들만 'NQ'에 저장되어 있을 것이다.

  

2) 지금까지 위에서 한 내용들은 실제로 치즈를 녹이기 전 준비작업과 같은 단계들이였다.

   이제는 실제로 치즈를 녹이는 과정을 진행할 것이다. 언제까지 ? 모든 치즈가 다녹을때까지 !

   치즈를 녹이는 과정은 다음과 같다.

   1. 외부에 존재하는 공기들 중, 치즈와 인접한 공기들만 저장해놓은 'NQ'를 또 다른 Queue에 복사한다.

     이 후, NQ는 모두 비워준다. 지금부터 NQ를 복사해놓은 또 다른 Queue를 'Q'라고 부르겠다.

   2. 인접한 4방향을 탐색하면서 치즈가 있으면, 치즈의 좌표 값을 1 에서 0으로 바꿔주고,

     그 값을 'Q가 아닌 ! NQ에 넣어준다'

   3. Q가 모두 빌 때 까지 2번 탐색을 진행한다.

   그럼 2번에서 찐하게 표시된 'Q가 아닌 NQ에 넣는 과정' 이 무슨말을 의미하는지 생각해보자.

   우리는 지금 'NQ'에 "치즈와 인접한 공기들"만 저장해 주었다. 이 말이 무슨말일까 ??

   '치즈가 여러겹으로 존재할 수 있는데, 치즈의 가장 바깥쪽과 인접한 공기' 들을 저장해 주었다는 의미이다.

   그럼, 치즈가 여러겹이라고 가정해보자. 'NQ'에 의해서 치즈가 가장 바깥쪽이 녹았으면 그 다음에 있는 치즈를

   녹일 수 있는 공기는 어디에 있을까 ?? 가장 바깥쪽에 위치해 있는 치즈의 위치에 있을 것이다.

   무슨 소린지 하나도 모르겠으니 그림으로 한번 이해해보자.

  

   위의 그림 상황을 한번 살펴보자.

   노랑색으로 칠해진 칸들이 아마 'NQ'에 들어있는 "치즈와 인접해있는 공기" 들일 것이다.

   그리고 그 공기들에 의해서 빨강색으로 표시된 치즈들은 녹게 될 것이다.

   그럼 파랑색의 치즈를 녹이기 위한 공기는 어디에 위치하게 될까 ??

   바로 빨강색으로 표시된 치즈들이 있는 위치가 그 공기들의 위치가 될 것이다.

   이 부분 때문에 'NQ'에 사라지는 치즈들의 좌표를 저장해준 것이다.

   왜냐하면 그 다음 치즈들을 녹일 때, 그대로 NQ를 사용하면 되기 때문이다.

  

   그럼 왜 이렇게 짰을까 ?? 탐색 시간을 줄이기 위해서이다. 사실, 맵 전체를 돌면서 외부공기들을 다 찾은 후에

   치즈를 녹이고, 그 다음턴에 다시 외부공기들을 다 찾은 후에 치즈를 녹이고... 이렇게 반복을 한다고 하더라도

   답은 나올것이다. 시간초과에 걸리는지는 본인도 해보지 않아서 잘 모르겠다.

   본인은 이 탐색 시간을 줄이기 위해서 'NQ'와 같은 또 다른 하나의 큐를 더 사용한 것이다.

   즉, "치즈를 녹임과 동시에 그 다음 치즈를 녹일 공기의 좌표를 저장한 것이다."

  

3) 그럼 위의 과정들만 반복해주면 될까?? 한가지 빠진게 있다. 바로 '내부에 존재하는 공기'이다.

   치즈가 점점 녹으면서 처음에는 내부에 존재한 공기였지만, 외부의 공기와 만나게 되는 상황도 발생할 것이다.

   이 부분도 'NQ'를 이용해서 쉽게 찾을 수 있다.

   지금 어디까지 했는지 지금 어떤 상황인지 간단하게 정리를 해보자.

   1. 외부와 내부 공기를 나눴고, 외부공기 중에서도 치즈와 인접한 공기를 NQ에 저장시켜놨다.

   2. NQ를 모두 비운 후, 치즈를 녹이면서 동시에 다시 NQ에 그 좌표들을 저장해주었다. 왜냐하면 그 좌표가 그 다음

     치즈들을 녹일 공기가 존재하는 좌표이기 때문에 !

   지금 여기까지 온 것이다. 그럼 지금부터 'NQ'를 가지고 BFS탐색을 실행하는 것이다.

   탐색조건은 Visit의 값이 0인 좌표라면 탐색진행 ! 이다.

   왜 ?? 초기에 치즈가 있던 좌표는 Visit의 값을 -1로, 외부공기가 있는 곳은 Visit의 값을 1로, 내부공기가 있는 곳은

   Visit의 값을 0으로 설정해놨다. 즉, 'NQ'에서 탐색을 하다가 Visit가 0인 좌표를 만난다면 ? 그 말은 즉, 내부공기였지만

   이제는 내부와 통하게 되었다 라는 것을 의미한다.

  

   설명이 길어졌는데, 위와 같이 구현을 해 주었다.

   그럼 정답은 어떻게 출력할까 ?? 이 또한 ! 'NQ'로 쉽게 찾을 수 있다. 바로 'NQ'의 Size가 녹기 1초전의 치즈의

   갯수가 된다.

  

   맵이 이렇게 주어졌을 때 답은 뭘까 ? 답은 아마 1초 후에 모든 치즈가 녹고, 녹기 1초전 치즈의 갯수는 8개 가 정답일

   것이다. 그럼 치즈가 한번 녹은 후에 NQ에는 몇 개의 좌표가 들어가 있을까?

   바로 치즈의 갯수인 8개가 들어가 있을 것이다.

   즉, 정답도 NQ를 이용해서 쉽게 찾을 수 있다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<stdio.h>
#include<cstring>
 
#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<int, int>> Air;
queue<pair<int, int>> NQ;
 
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)
            {
                Visit[i][j] = -1;    // 입력과 동시에 치즈가 있는 좌표는 -1로 표시
            }
        }
    }
}
 
void First_Air_State()
{
    /* 외부 공기와 내부 공기를 분리하는 작업. */
    /* Visit[][] 배열의 초기값은 0 이고, 이 중에서 외부공기만 1로 바꿔준다. */
    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 (MAP[nx][ny] == 0 && Visit[nx][ny] == 0)
                {
                    Visit[nx][ny] = 1;
                    Q.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Divide_Air()
{
    /* 외부 공기 중에서도, 치즈와 인접한 공기와 그렇지 않은 공기를 나누는 작업. */
    /* 치즈와 인접한 공기는 'NQ'에 저장이 된다. */
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Visit[i][j] == 1)
            {
                for (int k = 0; k < 4; k++)
                {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < M)
                    {
                        if (MAP[nx][ny] == 1)
                        {
                            NQ.push(make_pair(i, j));
                            break;
                        }
                    }
                }
            }
        }
    }
}
 
void Melting_Cheese()
{
    /* 치즈를 실제 녹이는 과정. 
     * 1. NQ에 값들을 복사하고 NQ를 비워준다.
     * 2. 치즈가 있는 좌표는 치즈를 녹여주고, 해당 치즈의 좌표를 NQ에 넣어준다.
     */
    queue<pair<int, int>> Q = NQ;
    while (NQ.empty() == 0) NQ.pop();
    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 (MAP[nx][ny] == 1)
                {
                    MAP[nx][ny] = 0;
                    NQ.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
void Add_Air()
{
    /* 내부공기와 외부공기를 합치는 과정. */
    /* 현재 치즈와 인접한 외부공기는 NQ에 저장이 되어있으므로 
    /* 이 공기들의 좌표들로부터 BFS 탐색 실시.
     * 만약, 내부 공기를 만나게 되면 그 내부공기 또한 외부공기와 같은 역할을 할 수 있으므로
     * 그 공기들 또한 NQ에 저장 ! 
     */
    queue<pair<int, int>> Q = NQ;
    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));
                    NQ.push(make_pair(nx, ny));
                }
            }
        }
    }
}
 
bool Check()
{
    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()
{
    First_Air_State();
    Divide_Air();
 
    int Time = 0;
    int Final_Size = 0;
 
    while (1)
    {
        if (Check() == true) break;
        
        Melting_Cheese();
        Final_Size = NQ.size();
 
        Add_Air();
        Time++;
    }
    cout << Time << endl << Final_Size << 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;
}