[백준 7569] 토마토

🔗알고리즘 문제

이전에 해결하였던 토마토 문제와 유사한 문제로 쉽게 해결할 수 있었다.

문제 분석

이 문제는 3차원으로 쌓여있는 토마토 판의 정보가 주어질 때 모든 토마토가 익을 때까지 걸리는 날짜를 출력하는 문제이다. 하루가 지날 때마다 익은 토마토의 앞, 뒤, 오른쪽, 왼쪽, 위, 아래 여섯 방향의 안 익은 토마토가 익게 된다.

발상 & 알고리즘 설계

기본 로직 자체는 2차원 토마토 문제와 다를 것이 없어서 z축만 생각해주면 쉽게 해결할 수 있다.

얼핏보면 3차원 구조로 보이지만 토마토 판의 구조를 2차원 구조로 만들어 문제를 해결할 수 있다.

0 0 0 0 0	-	1층
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0	-	2층
0 0 1 0 0
0 0 0 0 0

n이 3, m이 5, h가 2일 때 다음과 같이 정보가 들어온다면 2차원 배열내에서 n별로 을 나눌 수 있다.

때문에 다음 노드를 탐사할 때 n만큼 더해주거나 빼준다면 층을 이동할 수 있다. 이러한 특성을 이용하여 z축까지 총 6방향을 탐사해주었다.

코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int destX[6] = { -1, 1, 0, 0, 0, 0 };
int destY[6] = { 0, 0, -1, 1, 0, 0 };

int arr[10001][101] = {};

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

    int n;
    int m;
    int h;

    int answer = 0;

    queue<pair<int, int>> q;

    cin >> m >> n >> h;
    destY[4] = -n;
    destY[5] = n;

    for(int i = 0; i < n * h; i++){
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
            if(arr[i][j] == 1){
                q.push({ j, i });
            }
        }
    }

    while(q.empty() == false){
        pair<int, int> node = q.front();
        q.pop();

        for(int i = 0; i < 6; i++){
            pair<int, int> next = { node.first + destX[i], node.second + destY[i]};

            if(next.first < 0 || next.first > m - 1 || next.second < 0 || next.second > n * h - 1)
                continue;

            if(i < 4 && node.second / n != next.second / n)
                continue;

            if(arr[next.second][next.first] == -1)
                continue;

            if(arr[next.second][next.first] != 0 && arr[next.second][next.first] <= arr[node.second][node.first] + 1)
                continue;

            arr[next.second][next.first] = arr[node.second][node.first] + 1;
            q.push(next);
        }
    }

    for(int i = 0; i < n * h; i++){
        for(int j = 0; j < m; j++){
            if(arr[i][j] == 0){
                cout << -1;
                return 0;
            }

            if(arr[i][j] > 0){
                answer = max(answer, arr[i][j]);
            }
        }
    }

    cout << answer - 1;
}