[BOJ_C++] 7569번: 토마토

CODE

#include <bits/stdc++.h>
using namespace std;
int board[102][102][102];
int dist[102][102][102];
int n, m, h, day;
int dx[6] = {1, 0, 0, -1, 0, 0};
int dy[6] = {0, 1, 0, 0, -1, 0};
int dz[6] = {0, 0, 1, 0, 0, -1};

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

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

    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 6; dir++){
            int nx = get<0>(cur) + dx[dir];
            int ny = get<1>(cur) + dy[dir];
            int nz = get<2>(cur) + dz[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h) continue;
            if(dist[nx][ny][nz] >= 0) continue;
            dist[nx][ny][nz] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
            q.push(make_tuple(nx, ny, nz));
        }
    }

    day = 0;
    for(int k=0; k<h; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(dist[i][j][k] == -1){
                    cout << -1;
                    return 0;
                }
                day = max(day, dist[i][j][k]);
            }
        }
    }

    cout << day;

    return 0;
}

풀이

 앞서 풀었던 7576 토마토와 풀이가 거의 비슷하다. (다른 점이라고는 높이가 생겼다는 정도) 토마토를 담을 3차원 배열을 선언한 뒤, 7576 토마토와 같은 원리로 1의 값을 가지는 보드는 큐에 넣고 0의 값을 가지는 보드 위치의 거리 배열은 -1을 넣는다. 이후 bfs를 통해 토마토간 거리를 계산한 뒤 -1이 있다면 -1을 없다면 가장 큰 값을 출력하면 된다.

결과