#include <iostream>
#include <utility> //pair
#include <queue>
using namespace std;
int map[101][101][101]; // 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토 없음
queue<pair<pair<int, int>, int> > q; // h, y, x
// 상하좌우위아래 탐색
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dh[6] = {0, 0, 0, 0, 1, -1};
bool allTomato = true; // 모든 토마토 익어있는 경우
int M, N, H; // 가로, 세로, 높이
int cnt = 0; // 토마토 모두 익을 때 까지 걸리는 시간
void BFS(){
while(!q.empty()){
int x = q.front().second;
int y = q.front().first.second;
int h = q.front().first.first; // 노드의 좌표 구하기
q.pop();
for(int i = 0; i < 6; i++){
int nx = x + dx[i];
int ny = y + dy[i];
int nh = h + dh[i];
if(nx < 1 || ny < 1 || nh < 1 || nx > M || ny > N || nh > H){
continue;
}
if(map[nh][ny][nx] == 0){ // 안익은 토마토가 있을 때
map[nh][ny][nx] = map[h][y][x] + 1; // 날짜 더하기
q.push({{nh, ny}, nx});
}
}
}
}
int main(int argc, char* argv[]){
scanf("%d %d %d", &M, &N, &H);
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
for(int k=1; k<=M; k++){
scanf("%d", &map[i][j][k]); // 입력받기
if(map[i][j][k] == 1){ // 익은 토마토일 때
q.push({{i, j}, k});
} else if(map[i][j][k] == 0){
allTomato = false;
}
}
}
}
if(allTomato){ // 처음부터 모든 토마토 익어있는 경우
printf("0");
return 0;
}
BFS();
// for(int i=1; i<=H; i++){
// for(int j=1; j<=N; j++){
// for(int k=1; k<=M; k++){
// printf("%d ", map[i][j][k]);
// }
// printf("\n");
// }
// }
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
for(int k=1; k<=M; k++){
if(map[i][j][k] == 0){ // 모두 익지 않았을 때
printf("-1");
return 0;
}
if(cnt < map[i][j][k]){ // 최대 일 수 구하기
cnt = map[i][j][k];
}
}
}
}
printf("%d", cnt-1); // 토마토 익은 것 1부터 시작
return 0;
}
7576 토마토의 업그레이드 버전 문제
상하좌우위아래 를 확인하기 위해서는 위로 갈 경우, 아래로 갈 경우, 좌로 갈 경우, 우로 갈 경우... 해서 6가지의 경우 수만 확인하면 된다. 이걸 조심하자. 처음에는 모든 경우의 수를 내가 배열에 넣어서 구하려고 했는데 굉장히 불필요한 일이었다.
cnt를 세기 위해 바로 map으로 표시했기에 visit 여부는 표시할 필요가 없다. 때문에 7576 번에서 푼 것과 다르게 이번에는 visited를 아예 빼버렸다.
pair에 값을 입력할 때, make_pair를 쓰는 것도 좋지만 {}를 쓰는 것이 훨씬 직관적이며 쉽다.