[백준][C++] 7569: 토마토

 

https://www.acmicpc.net/problem/7569

7569번: 토마토

 

 

 

 

 

---

- 문제

 

M x N x H 토마토 창고가 주어질 때, 익은 토마토의 상하좌우위아래에 있는 안 익은 토마토가 하루가 지남에 따라 익어갈 때, 모든 토마토가 익기 위해서 최소한 며칠이 필요한지 구하는 문제다.

 

 

---

- 해설

 

https://stopthebackspace.tistory.com/136

 

 

위의 문제가 M x N인 이차원 배열에서의 토마토 문제고,

 

이번 문제는 여기에 H 하나 추가한 3차원 배열에서의 토마토 문제다.

 

푸는 방식은 정확히 똑같지만, 차원이 하나 늘어났으니 주의하면 된다.

 

 

 

pair<int,int>

 

대신에 

 

tuple<int,int,int>를 사용하면 되고,

 

이걸 활용하는 방법은 queue에 있는 값을 뺄때

 

get<0>(q.front()) 와 같은 식으로 0,1,2를 사용해서 활용할 수 있다.

 

 

 

---

- 풀이

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int tomatoes[1001][1001] = {0};
bool visited[1001][1001] = {false};
int result[1001][1001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int M, N, cnt = 0, temp;
    int dirX[4] = {-1, 1, 0, 0};
    int dirY[4] = {0, 0, -1, 1};
    bool isAnswerPrinted = false;
    queue<pair<int, int>> q;

    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> temp;
            if (temp == 0)
            {
                cnt++; // 안 익은 토마토 몇개 있는지 세기
            }
            if (temp == 1)
            {
                q.push(pair<int, int>(i, j)); // 익은 토마토 위치 queue에 저장
                result[i][j] = 0;             // 각자 토마토 날짜 저장
            }
            tomatoes[i][j] = temp;
        }
    }
    while (!q.empty())
    {
        int nowX = q.front().first, nowY = q.front().second;
        q.pop();
        if (!visited[nowX][nowY] && tomatoes[nowX][nowY] >= 0) // 토마토에 처음 들리고 토마토가 있으면
        {
            visited[nowX][nowY] = true;
            if (tomatoes[nowX][nowY] == 0) // 토마토가 안 익은 토마토일때 세기
            {
                cnt--;
            }
            if (cnt == 0) // 모든 토마토가 익었으면 출력
            {
                isAnswerPrinted = true;
                cout << result[nowX][nowY];
                break;
            }
            for (int i = 0; i < 4; i++) // 상하좌우로
            {
                int newX = nowX + dirX[i], newY = nowY + dirY[i];
                if ((newX >= 0 && newX < N && newY >= 0 && newY < M) && tomatoes[newX][newY] == 0) // 박스를 벗어나지 않고 다음 토마토가 안 익은 토마토면
                {
                    q.push(pair<int, int>(newX, newY));
                    if (result[newX][newY] == 0)
                    {
                        result[newX][newY] = result[nowX][nowY] + 1; // 다음 토마토는 현재 토마토에 날짜 하나 더함
                    }
                }
            }
        }
    }
    if (!isAnswerPrinted) // 모든 토마토가 익지 않았을때
    {
        cout << -1;
    }
    return 0;
}

 

 

---

- 새롭게 알게 된 점