[Jungol] 정올 2606 토마토(초)

출처: Jungol 2606 토마토(초)

Approach

- 익은 토마토는 1개 이상일 수 있다.

- 비어있는 칸 너머에 있는 안 익은 토마토는 익힐 수 없다.

- Queue를 이용한 BFS → O(N x M x H)

 

 

📌 BFS (Breadth-First Search, 너비 우선 탐색) 

BFS (Breadth-First Search, 너비 우선 탐색)

 

 

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 102;
const int INF = LM * LM * LM;
int N, M, H, A[LM][LM][LM];
int dh[] = { -1, 1, 0, 0, 0, 0};
int dr[] = { 0, 0, -1, 1, 0, 0 };
int dc[] = { 0, 0, 0, 0, -1, 1 };
int tomato, fr, re;
struct Data{
    int h, r, c, lev;
}que[INF];
 
void push(int h, int r, int c, int lev){
    if (A[h][r][c] == 0)
        return;
    que[re++] = { h, r, c, lev };
    A[h][r][c] = 0;
    tomato--;
}
void input(){
    int i, j, k, v;
    scanf("%d %d %d", &N, &M, &H);
    for (i = 1; i <= H; i++) 
        for (j = 1; j <= M; j++) 
            for (k = 1; k <= N; k++) {
                scanf("%d", &v);
                v++;
                A[i][j][k] = v;
                if (v > 0) tomato++;
                if (v == 2) push(i, j, k, 0);
            }
}
 
int BFS(){
    Data t;
    while (fr < re){
        t = que[fr++];
        for (int i = 0; i < 6; i++){
            push(t.h + dh[i], t.r + dr[i], t.c + dc[i], t.lev + 1);
        }
    }
    if (tomato) 
        return -1;
    
    return t.lev;
}
 
int main(){
    //freopen("input.txt", "r", stdin);
    input();
    printf("%d\n", BFS());
}