#7569 토마토 (C++) 🍅

링크 : www.acmicpc.net/problem/7569

7569번: 토마토

이 문제는 #7576번 토마토의 확장판이다.

풀이 방식은 7576번과 큰 차이가 없다. 다만 입력받는 배열에 Z축이 하나 추가되었을 뿐이다.

 

문제 풀이는 다음과 같다.

 

1. 배열을 2개 만든다. 하나는 값을 입력받을 값(arr), 다른 하나는 방문 여부를 파악하고 동시에 토마토가 익을 날짜를 누적할 배열(ch)이다.
2. 배열에 값을 넣는다. 이때 ch(방문여부를 파악하며 동시에 가 토마토익는 날짜를 누적)는 모두 -1로 채워넣는다. 
3. 배열에 입력된 값이 '1'일 경우(즉, 익은 토마토이다), 해당 배열의 쌍을 큐에 넣어주고 ch값은 0으로 넣는다. 
4. 상 / 하 / 좌 / 우 / 위 (z축) / 아래 (z축) 로 🍅 가 익을 수 있는 루트를 BFS한다. 만약 해당 위치의 배열값이 '0'이고 (토마토가 아직 안익음), check값이 -1이라면 (방문한 적이 없음을 의미) 해당 값을 큐에 넣어준다. 
5. 동시에 해당 값의 ch배열에 이전 값의 + 1을 해주어 넣는다. 즉, 이전 값보다 하루가 누적되어 토마토가 익었음을 의미한다. 
6. for문을 돌려서 가장 큰 값의 check를 출력하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int m = 0, n = 0, h = 0, ny = 0, nx = 0, nz = 0, y = 0, x = 0, z = 0, ans = -1;
int arr[101][101][101], ch[101][101][101]; // z, y, x
int my[4] = { 0,1,0,-1 };
int mx[4] = { -1,0,1,0 };
int mz[2] = { -1,1 };

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

    cin >> m >> n >> h;
    queue<pair<int, pair<int, int>>> q;
    for (int x = 1; x <= h; x++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> arr[x][i][j];
                ch[x][i][j] = -1;
                if (arr[x][i][j] == 1) {
                    q.push(make_pair(x, make_pair(i, j)));
                    ch[x][i][j] = 0;
                }
            }
        }
    }
    while (!q.empty()) {
        nz = q.front().first;
        ny = q.front().second.first;
        nx = q.front().second.second;
        q.pop();
        for (int i = 0; i < 6; i++) {
            if (i < 4) {
                y = ny + my[i];
                x = nx + mx[i];
                if (y <= n && y >= 1 && x <= m && x >= 1) {
                    if (arr[nz][y][x] == 0 && ch[nz][y][x] == -1) {
                        q.push(make_pair(nz, make_pair(y, x)));
                        ch[nz][y][x] = ch[nz][ny][nx] + 1;
                    }
                }
            }
            else {
                z = nz + mz[i - 4];
                if (z >= 1 && z <= h) {
                    if (arr[z][ny][nx] == 0 && ch[z][ny][nx] == -1) {
                        q.push(make_pair(z, make_pair(ny, nx)));
                        ch[z][ny][nx] = ch[nz][ny][nx] + 1;
                    }
                }
            }
        }
    }
    for (int x = 1; x <= h; x++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (arr[x][i][j] == 0&&ch[x][i][j]==-1) {
                    cout << -1 << "\n";
                    return 0;
                }
                if (ch[x][i][j] > ans) ans = ch[x][i][j];
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

 

 

 

크게 어려울건 없었으나, 변수가 이전보다 늘어나서 헷깔리는 부분이 있었다.