7569 백준 토마토

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

7569번: 토마토

#include <iostream>
#include <tuple>
#include <queue>

using namespace std;

int box[102][102][102];
int dist[102][102][102];


//위 아래 좌 우 앞 뒤 순
int ny[6]={0, 0, -1, 1, 0, 0};
int nx[6]={0, 0, 0, 0, 1, -1};
int nz[6]={-1, 1, 0, 0, 0, 0};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int m, n, h;
    int ans=0;

    cin >> m >> n >> h;

    queue<tuple<int, int, int>> q;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                cin >> box[i][j][k];
                if (box[i][j][k] == 1) {
                    q.push(make_tuple(i, j, k));
                }
                if (box[i][j][k] == 0) {
                    dist[i][j][k] = -1;
                }
            }
        }
    }

    while (!q.empty()) {

        tuple<int, int, int> cur = q.front();
        int cnt = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)];
        q.pop();

        for (int i = 0; i < 6; i++) {
            int newY = get<0>(cur)+ny[i];
            int newX = get<1>(cur)+nx[i];
            int newZ = get<2>(cur)+nz[i];

            //범위 체크
            if (newY >= 0 && newY < h && newX >= 0 && newX < n && newZ >= 0 && newZ < m) {
                //토마토 상태 체크
                if (dist[newY][newX][newZ] < 0) {
                    dist[newY][newX][newZ] = cnt + 1;
                    q.push(make_tuple(newY, newX, newZ));

                }
            }

        }

    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++) {
                //익지 않은 토마토 확인
                if (dist[i][j][k]==-1) {
                    cout << -1;
                    return 0;
                }

                ans = max(ans, dist[i][j][k]);

            }
        }
    }

    cout << ans;




    return 0;
}

 

 3차원 배열 bfs 문제이다. 

이미 익어있는 토마토부터 bfs를 돌리면서 거리를 구하고, 모든 토마토가 익어야 하므로 dist의 최댓값이 정답으로 출력된다. 인덱스가 3개의 숫자로 들어가므로 tuple을 사용하여 구현하였다.

 

 참고: c++ 튜플 사용법

#include <tuple>
#include <iostream>
#include <string>

using namespace std;

int main() {
    tuple<int, double, string> tup(0, 1.42, "Call me Tuple");

    // get elements by index
    cout << " " << get<0>(tup);
    cout << " " << get<1>(tup);
    cout << " " << get<2>(tup) << endl;

    // get elements by type
    cout << " " << get<int>(tup);
    cout << " " << get<double>(tup);
    cout << " " << get<string>(tup) << endl;
}

위와 같이 선언하고 순서, 타입으로 값을 뽑아낼 수 있다. 

get<T>(tup)의 경우 같은 타입의 값이 두 개 이상 있으면 오류가 발생한다.