[백준 7569] 토마토(C++)

📕문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

📕입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M, N과 쌓아 올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

---

📕출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

---

💡문제해석

• 토마토가 모두 다 익을 수 있는 최소의 일수를 구한다는 것이 문제의 목표이다.
  • 우리는 최솟값, 최소 경로를 구하기 위해서는 DFS보단 BFS가 효율적이라는 것을 이전 알고리즘 소개에서 배웠을 것이다.
• 문제 특성상 3차원 배열로 푸는 게 쉬울 거 같아서 모든 배열을 3차원 배열로 해결했다.
• 익은 토마토의 위치를 queue에 넣어줌.
• queue에서 front에서 뽑고 pop 하고 경로 체크와 토마토 체크를 한 뒤 date와 visit, tomato를 각각 업데이트해주고, queue에 넣는다.
• queue가 빌 때까지 과정을 했는데 만약 빈 토마토가 있다면 -1을 출력 아니라면 해당 날짜를 출력함.

 

👀구현

1. 변수 선언

• tomato는 익은 토마토, 안 익은 토마토, 빈 장소를 각각 넣음.
• visit은 방문을 했는지, 안 했는지의 여부를 검사.
• date는 며칠 차인지를 검사함.
• 방향은 총 6가지 방향이 있다. [왼쪽, 오른쪽, 아래, 위, 앞, 뒤]
  • 방향 설정에 유의하자. 방향설정 때문에 계속 틀렸었다..!

2. 행렬 만들기

• 토마토가 익은 토마토 라면 해당 위치를 queue에 넣어줌.
• pair(i*m+j, k) 해준 이유는 나중에 쉽게 자기 좌표를 역 추적할 수 있기 때문이다.
• 아래 그림처럼 나는 좌표를 숫자로 변환해서 넣어줬다.
• 만약 (2,2) -> 8  왜냐하면 2(row)*(세로의 개수)+2(col)이기 때문.

3.BFS 함수 설명

• queue에 front에 있는 좌표를 뽑아서 변수에 저장 후 pop 해준다.
• 방향은 총 6가지 방향이 있고, 옮겨준 좌표가 이동할 수 없는 index라면 continue 해준다.
• 이동할 수 있는 경우 그 이동한 좌표의 토마토가 익지 않았고, 방문을 하지 않았다면 토마토가 익었다는 표시를 하고, 방문했다는 표시를 하고 날짜를 최신화해준다.

4. 답 출력

• 만약 행렬을 탐색해서 안 익은 토마토가 있다면 day에 -1을 저장하고, 만약 안익은 토마토가 없다면 원래 저장된 day를 출력함.

📜코드

/*
백준 7569 골드5
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int n, m, h, answer = -1, day = 0; // N = 상자 세로 칸의 수 M = 상자 가로 칸의 수 H = 상자의수
vector<vector<vector<int>>> tomato;
vector<vector<vector<int>>> date;
vector<vector<vector<int>>> visit;
queue<pair<int, int>> Tomato;
vector<int> x = { 0, 1, -1, 0, 0, 0 }, y = { 1, 0, 0, -1, 0, 0 }, z = { 0, 0, 0, 0, 1, -1 };
void tom();
int main()
{
    cin >> m >> n >> h;
    tomato.resize(n, vector<vector<int>>(m, vector<int>(h, 0)));
    visit.resize(n, vector<vector<int>>(m, vector<int>(h, 0)));
    date.resize(n, vector<vector<int>>(m, vector<int>(h, 0)));
    for (int k = 0; k < h; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int num = 0;
                cin >> num;
                tomato[i][j][k] = num;
                if (num == 1)
                {
                    Tomato.push(make_pair(i * m + j, k)); //해당 행렬에서 좌표를 특정위치로 삼아서 넣고, k를 넣어줌.
                }
            }
        }
    }
    if (Tomato.size() == m * n)
    {
        cout << 0;
        return 0;
    }
    tom();
    //토마토가 익은 부분을 queue에 넣어줌.
}
void tom()
{
    while (!Tomato.empty())
    { // tomato가 완전히 빌떄까지 반복한다.
        //첫번째를 선택함.
        int xx = Tomato.front().first;  // x,y좌표 합쳐놓은거 i*m+j
        int zz = Tomato.front().second; // z좌표
        int col = xx % m, row = xx / m; //실제 좌표를 구했음.
        //cout << "현재 익은 토마토위치는 " << row << " " << col << " " << zz << endl;
        Tomato.pop(); //선정하고 뺀다.
        //여기서 갈 수 있는 방향과 그 때 갔을 때 토마토의 값이 0이면 1로 바꿔줘야함.
        for (int i = 0; i < 6; i++)
        {
            int dx = row + x[i], dy = col + y[i], dz = zz + z[i]; //움직이는 좌표가 잘못된듯.. 바로 위랑 아래만 가능하네.
            if (dx < 0 || dx >= n || dy < 0 || dy >= m || dz < 0 || dz >= h)
            { //해당 방향으로 못가요 ~
              // cout << dx << " " << dy << " " << dz << " 해당 방향은 index가 터지기 때문에 못갑니다" << endl;
                continue;
            }
            //만약 갈 수 있다면?
            if (tomato[dx][dy][dz] == 0 && visit[dx][dy][dz] == 0)
            { //해당 자리에 토마토가 있다면?
                tomato[dx][dy][dz] = 1;
                visit[dx][dy][dz] = 1;
                date[dx][dy][dz] = date[row][col][zz] + 1;
                //cout << dx << " " << dy << " " << dz << " 토마토 찾앗다! " << date[dx][dy][dz] << endl;
                if (day < date[dx][dy][dz])
                {
                    day = date[dx][dy][dz];
                }
                Tomato.push(make_pair(dx * m + dy, dz));
            }
        }
    }
    for (int k = 0; k < h; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (tomato[i][j][k] == 0) //만약 안익은 토마토가 있다면? -1로 해줘야함.
                {
                    // cout << "안익은 토마토가 있습니다" << endl;
                    day = -1;
                    break;
                }
            }
        }
    }
    cout << day << endl;
}

✔느낀 점

• 확실히 이론 정리를 하고 문제를 접근하니 무슨 방법을 써야 할지 바로 느낌이 와서 시간을 많이 단축했다.
• 문제를 이해하는데 조금 고생을 했다.(방향이랑 일차)
• 이해하고 보면 문제를 구성하는 알고리즘 자체는 쉬운 편이다.