[백준] 7569번: 토마토

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

7569번: 토마토

문제이해

https://chagaun-omija.tistory.com/74

[백준] 7576번: 토마토

여기 있는 토마토 문제랑 거의 똑같은데, 토마토 상자들이 3차원이 되었다는 점이 다르다. 

고로 BFS를 하되, 방향을 4방향이 아닌 상하좌우 + 위, 아래 를 해줘야 한다.

그거 외엔 어려운 점 없음!

 

작성 코드 (C)

#include <stdio.h>
#define MAXN 100

int M, N, H;
int map[MAXN + 5][MAXN + 5][MAXN + 5];
int visited[MAXN + 5][MAXN + 5][MAXN + 5];
int tomato;
typedef struct ele {
	int h, y, x, t;
}ELE;
ELE q[MAXN * MAXN * MAXN * 10];
int wp, rp;
void enq(int h, int y, int x, int t) {
	q[wp].h = h;
	q[wp].y = y;
	q[wp].x = x;
	q[wp++].t = t;
}
ELE deq(void) {return q[rp++];}
int empty(void) { return wp == rp; }

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

void Get_Input(void) {
	scanf("%d %d %d", &M, &N, &H);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				scanf("%d ", &map[i][j][k]);
				if (map[i][j][k] == 0) tomato++;
			}
		}
	}
}

int BFS(void) {
	int cnt = 0; 
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				if (map[i][j][k] == 1) {
					enq(i, j, k, 0);
					//visited[i][j][k] = 1;
				}
			}
		}
	}

	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 6; i++) {
			int nh = dh[i] + cur.h;
			int ny = dy[i] + cur.y;
			int nx = dx[i] + cur.x;
			if (nh < 0 || nh >= H || ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (map[nh][ny][nx] != 0) continue;
			// 익지 않은 토마토
			map[nh][ny][nx] = cur.t + 1;
			enq(nh, ny, nx, cur.t + 1);
			cnt++;
		}
	}
	return cnt;
}

int main(void) {
	freopen("in.txt", "r", stdin);
	Get_Input();
	int cnt = BFS();
	if (cnt < tomato) printf("-1");
	else printf("%d", q[wp - 1].t);
	return 0;
}