[알고리즘/문제풀이][BOJ 7569번] 토마토

7569번 토마토는 전에 풀었던 토마토 문제를 확장한 문제입니다. 토마토를 보관하는 상자를 위로 쌓을 수 있도록 하였기 때문에 너비우선탐색을 할 때 상하좌우 뿐만 아니라 위, 아래 방향으로도 탐색을 해야 합니다. 탐색의 방향이 추가된 것을 제외하면 기존 토마토 문제와는 모든 부분이 똑같습니다.

이전에 풀었던 토마토 문제는 다음 글에서 확인할 수 있습니다.

2021.09.12 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 7576번] 토마토

[알고리즘/문제풀이][BOJ 7576번] 토마토

문제를 풀기 위해 작성한 코드는 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com

int dx[] = { 0,0,-1,1,0,0 };
int dy[] = { 1,-1,0,0 ,0,0};
int dz[] = { 0,0,0,0,1,-1 };
int N, M, H;
int map[120][120][120];
int wp, rp;

int cnt = 0;


struct Queue {
	int x, y, z, time;
};

struct Queue queue[100*100*100];
struct Queue temp;

void enqueue(int x, int y, int z, int time) {
	queue[wp].x = x;
	queue[wp].y = y;
	queue[wp].z = z;
	queue[wp].time = time;
	wp++;
}

struct Queue dequeue() {
	return queue[rp++];
}

int empty() {
	return wp == rp;
}

int main(void) {
	scanf("%d %d %d", &M, &N, &H);

	for (int k = 0; k < H; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				scanf("%d", &map[k][i][j]);
				if (map[k][i][j] == 1) {
					enqueue(j, i, k, 0);
				}
				else if (map[k][i][j] == 0) {
					cnt++;
				}
			}
		}
	}
	if (cnt == 0) {
		printf("0\n");
		return 0;
	}

	while (!empty()) {
		temp = dequeue();
		for (int i = 0; i < 6; i++) {
			int nx = temp.x + dx[i];
			int ny = temp.y + dy[i];
			int nz = temp.z + dz[i];
			if ((nx < 0) || (nx >= M)) continue;
			if ((ny < 0) || (ny >= N)) continue;
			if ((nz < 0) || (nz >= H)) continue;
			if (map[nz][ny][nx] != 0) continue;
			enqueue(nx, ny, nz, temp.time + 1);
			map[nz][ny][nx] = 1;
		}
	}

	cnt = 0;
	for (int k = 0; k < H; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[k][i][j] == 0) {
					printf("%d\n", -1);
					return 0;
				}
			}
		}
	}
	printf("%d\n", temp.time);
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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