백준 7569: 토마토

문제 요약

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.(3차원 배열)

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS

문제 풀이

BFS로 풀면 되는 문제이다. [C++] 백준 7576: 토마토를 3차원으로 변형한 문제이다. 해당 포스트의 코드를 대부분 사용하였으며, 3차원으로 변형한 것만 빼면 똑같다. 자세한 건 해당 포스트를 참고

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

queue<pair<short, pair<short,short>>> q;
bool visited[100][100][100];
int ary[100][100][100];
const short dir[6][3] = { {0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0} };

int main()
{
	int h, n, m, level = -1, cnt = 0, qsize;
	short f, s, z, nextZ, nextF, nextS;
	cin >> m >> n >> h;
	for (short i = 0; i < h; i++) {
		for (short j = 0; j < n; j++) {
			for (short k = 0; k < m; k++) {
				scanf("%d", &ary[i][j][k]);
				if (ary[i][j][k] == 1) {
					q.push({ i, {j,k} });
					visited[i][j][k] = true;
				}
				else if (!ary[i][j][k]) cnt++;
			}

		}
	}
	while (!q.empty()) {
		level++;
		qsize = q.size();
		while (qsize--) {
			z = q.front().first;
			f = q.front().second.first;
			s = q.front().second.second;
			q.pop();
			for (int i = 0; i < 6; i++) {
				nextZ = z + dir[i][0];
				nextF = f + dir[i][1];
				nextS = s + dir[i][2];
				
				if (nextF >= 0 && nextF < n && nextS >= 0 && nextS < m && nextZ >= 0 && nextZ < h) {
					if (!ary[nextZ][nextF][nextS] && !visited[nextZ][nextF][nextS]) {
						cnt--;
						q.push({ nextZ, {nextF,nextS } });
						visited[nextZ][nextF][nextS] = true;
					}
				}
			}
		}
	}
	if (cnt == 0) printf("%d", level);
	else printf("-1");
	return 0;
}