[백준] 토마토 7569번 (c++)

출처 : 7569번: 토마토 (acmicpc.net)

7569번: 토마토

풀이 방법

다른 문제들과 달리 3차원 상황이다.

2차원과 비슷한 방법으로 방향 배열을 만들어 주면 된다.

int dy[6] = {0, 0, -1, 1, 0 ,0};
int dx[6] = {0, 0, 0, 0, -1, 1};
int dz[6] = {1, -1, 0, 0, 0, 0}; 

입력을 받으면서 익은 토마토가 나오면 q에 좌표를 추가해 주고

입력을 받은 후 bfs를 실행하면 된다

실행 후 check 함수를 통해 안 익은 토마토가 있으면 -1을 출력해주고 

없으면 걸린 일수를 출력 하면 된다

#include <bits/stdc++.h>
using namespace std ;

int max_h = 0;
int board[100][100][100], visited[100][100][100];
int dy[6] = {0, 0, -1, 1, 0 ,0};
int dx[6] = {0, 0, 0, 0, -1, 1};
int dz[6] = {1, -1, 0, 0, 0, 0};
int M, N, H, ans = 1;
queue<pair<int, pair<int, int>>> q;

int check() {
    for (int i = 0;i < H; i++) {
            for (int k = 0;k < N;k++) {
                for (int j = 0;j < M;j++) {
                    if (board[i][k][j] == 0) {
                        return 1;
                    }
                }
            }
    }
    return -1;
}

void bfs() {

    while (!q.empty()) {
        int zz = q.front().first;
        int yy = q.front().second.first;
        int xx = q.front().second.second;
        q.pop();
        for (int i = 0;i < 6;i++) {
            int nz = zz + dz[i];
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if (nz >= 0 && nz < H && ny >= 0 && ny < N && nx >= 0 && nx < M && visited[nz][ny][nx] == -1 && board[nz][ny][nx] == 0) {
                visited[nz][ny][nx] = 1;
                board[nz][ny][nx] = board[zz][yy][xx] + 1;
                q.push(make_pair(nz, make_pair(ny, nx)));
                if (ans < board[nz][ny][nx]) {
                    ans = board[nz][ny][nx];
                }
            }
        }
    }
}

int main () {
    memset(visited, -1, sizeof(visited));
    cin >> M >> N >> H;
    for (int i = 0;i < H; i++) {
            for (int k = 0;k < N;k++) {
                for (int j = 0;j < M;j++) {
                    cin >> board[i][k][j];
                    if (board[i][k][j] == 1) {
                        q.push(make_pair(i, make_pair(k, j)));
                    }
                }
            }
    }
    bfs();
    int  fail_case = check();
    if (fail_case == 1) {
        cout << -1 << endl;
    }
    else {
        cout << ans - 1;
    }
    return 0;
}