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

📕문제

---

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X 친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

 

<그림 1> 원래 치즈 모양

 

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 2> 한 시간 후의 치즈 모양

 

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

📕입력

---

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

📕출력

---

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

🔎문제 해석

---

외부 공기와 내부 공기를 분리시키는 작업이 중요한 문제이다. 

내부 공기는 치즈에 영향을 주지 않지만, 외부 공기는 치즈에 영향을 주기 때문이다.

공기를 구분 한뒤 그 외부 공기와 맞닿은 지역을 녹이는 작업을 계속하면 된다.

나는 BFS를 사용해서 풀었다.

 

💡초기 풀이 방식

1. 입력받은 배열중 0은 공기, 1을 치즈라고 생각했다.
   1. 치즈에 해당하는 부분은 queue에 푸쉬했다.
2. 그다음에 bfs를 돌렸다.

  🛑문제점

1. 내부 공기와 외부 공기를 분리를 시키지 않아서 문제가 풀리지 않았다.

💡수정 풀이 방식

1. 외부 공기와 내부 공기를 구분했다.
   1. 내부 공기는 치즈에 영향을 주지 않기 때문이다.
2. 배열을 입력받는 과정에서 만약 그 위치가 치즈라면[값이 1이라면] 그 좌표에 대한 visit값을 0으로 세팅해주고, queue에 넣어주고, 치즈의 조각을  +1 해줌.
   1. 초기 치즈의 조각도 계산해줄 필요가 있다. [아예 녹일 수 없는 상황이라면 그 초기의 치즈 개수가 최종 치즈의 개수이기 때문이다.] -> 이것은 문제를 풀다 보면 이해할 수 있을 것이다. 마지막 테케가 아예 녹이지 못하게 되는 경우라서 꼭 이 작업을 해줘야 한다!
3. visit배열을 새로 만들었다. [초기 값은 내부 공기에 해당하는 값을 세팅해줌]
   1. 세팅 값 : 2=내부 공기, 1 = 외부 공기, 0 = 치즈
4. 내부 공기를 뽑는 방법은 (0,0)에서 출발해서 0으로만 이동을 쭉쭉한다. [BFS 사용]
5. 외부 공기와 인접하는 치즈들을 녹이는 작업을 시작한다.
   1. 기본적으로는 BFS 작업.
   2. 상하좌우로 이동한 뒤 적절한 이동이고, 근처에 좌표 중 하나라도 공기가 있다면 치즈를 녹임
6. 녹인 뒤 시간을 +1 해준다.
7. 사용한 queue를 초기화해주고, visit 배열도 다시 초기화해준다.
8. 그리고 다시 2,3,4,5,6,7 작업을 반복한다.
9. 그러다가 만약 모든 배열에 값이 0이라면 [치즈가 다 녹았다면] 빠져나와서 결과값을 출력함.

💻코드

/*
2306 골드4 치즈
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, m;
vector<vector<int>> graph;
vector<vector<int>> visit;
queue<pair<int, int>> q;
queue<pair<int, int>> chese;
vector<pair<int, int>> air;
vector<int> x = {0, 0, 1, -1};
vector<int> y = {1, -1, 0, 0};
int t = 0, piece = 0, number = 0, result;
void outside_air();
void melting();
bool check();
int main()
{
    cin >> n >> m;
    graph.resize(n, vector<int>(m, 0));
    visit.resize(n, vector<int>(m, 2));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> graph[i][j];
            if (graph[i][j] == 1)
            { //치즈 위치를 queue에 넣음.
                q.push(make_pair(i, j));
                piece++;
                visit[i][j] = 0; //치즈는 0으로 초기화.
            }
        }
    }
    // graph랑 visit 배열 설정 위에서햇음.
    while (1)
    {
        if (check() == true)
        { //전부다 공기라면 반복문을 멈춘다.
            break;
        }
        result = piece;
        piece = 0;
        outside_air(); //외부공기를 visit값을 1로 초기화
        melting();     //외부공기와 맞닿은 치즈를 녹여줌. 해당 좌표를 graph 0값으로 돌림.
        t++;           //녹였으면 t++해줌.
        //녹이고 치즈 개수 세야함.
        while (!q.empty())
        { // queue 초기화.
            q.pop();
        }
        visit.assign(n, vector<int>(m, 2));
        for (int i = 0; i < n; i++)
        { // visit 배열에서 치즈 위치를 queue에 넣고, 치즈 위치를 visit에서 0으로 초기화
            for (int j = 0; j < m; j++)
            {

                if (graph[i][j] == 1)
                {
                    piece++; //치즈 기록.
                    q.push(make_pair(i, j));
                    visit[i][j] = 0;
                }
            }
        }
    }
    cout << t << endl; //다 녹인 시점 전에 시간을 출력
    cout << result;   //그 시간대에 치즈 조각들을 출력
}
bool check()  //배열에서 치즈가 다 녹았는지 안녹았는지 체크를 해줌.
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (graph[i][j] == 1)
            { //치즈가 있다면
                return false;
            }
        }
    }
    return true;
}
void outside_air() //외부 공기를 솎아 내는 작업
{
    queue<pair<int, int>> out;
    out.push(make_pair(0, 0)); //초기 좌표 넣어줌.
    while (!out.empty())
    {
        int tx = out.front().first;
        int ty = out.front().second;
        // cout<<"현재 좌표 : "<<tx<<" "<<ty<<endl;
        out.pop();
        for (int i = 0; i < 4; i++)
        {
            int row = tx + x[i];
            int col = ty + y[i];
            //  cout<<"move :"<<row<<" "<<col<<endl;
            if (row < 0 || col < 0 || row >= n || col >= m)
            {
                continue;
            }
            if (graph[row][col] == 0 && visit[row][col] == 2)
            { //갈려는 곳이 치즈가 아니고, 아직 방문 안했던 곳이라면
                out.push(make_pair(row, col));
                visit[row][col] = 1; //외부 공기는 1로 초기화.
            }
        }
    }
}
void melting() //외부공기랑 맞닿은 지역을 녹이기.
{
    queue<pair<int, int>> melt = q; // melt에는 치즈가 들어있음.
    while (!melt.empty())
    {
        int mx = melt.front().first;
        int my = melt.front().second;
        melt.pop();
        // chese 초기 위치 뽑아줌.
        for (int i = 0; i < 4; i++)
        { //좌표 이동
            int tempx = mx + x[i];
            int tempy = my + y[i];
            if (tempx < 0 || tempy < 0 || tempx >= n || tempy >= m)
            {
                continue;
            }
            if (visit[tempx][tempy] == 1)
            {                      //외부 공기와 맞닿아있다면
                graph[mx][my] = 0; // graph상에서 치즈를 공기로 바꿔줍니다.
            }
        }
    }
}

 

✔느낀 점

• 신선한 문제였다.
• 100%에서 틀리길래 뭔가 했는데 모든 배열이 1111111111111111111 즉 치즈로 채워진 경우에는 내가 생각을 안 해줘서 100%에서 틀린 거 같다.
• BFS는 이제 좀 할만할지도..?