BFS 및 DFS - 백준 7569번 토마토 (3차원)

www.acmicpc.net/problem/7569

7569번: 토마토

IDEA

7576번 토마토 ( blahblahlab.tistory.com/69 ) 문제를 그냥 3차원으로 푸는거일 뿐이다. 

아이디어는 똑같고 사방이 아닌 위아래까지 고려해 방향 6개를 고려하면 된다. 

CODE

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m,h;
int map[100][100][100];
int dx[] = { 1,-1,0,0 ,0,0};
int dy[] = { 0,0,-1,1 ,0,0};
int dz[] = { 0,0,0,0,-1,1 };

queue<pair<int, pair<int,int>>>tomato;

int check(int max_day) {
	int 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) cnt++;
			}
		}
	}
	if (cnt == 0) return max_day;
	else return -1;
}

int bfs() {
	int max_day = 0;
	while (!tomato.empty()) {
		int z = tomato.front().first;
		int x = tomato.front().second.first;
		int y = tomato.front().second.second;
		tomato.pop();
		for (int i = 0; i < 6; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];
			if (-1 < nx && nx < n && -1 < ny && ny < m &&  -1 < nz && nz < h && !map[nz][nx][ny]) {
				map[nz][nx][ny] = map[z][x][y] + 1;
				max_day = max(max_day, map[nz][nx][ny]);
				tomato.push({ nz,{nx, ny} });
			}
		}
	}
	return max_day - 1;
}

int main() {
	scanf("%d %d %d", &m, &n, &h);
	int zero_cnt = 0;
	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) tomato.push({k, { i , j }});
				if (map[k][i][j]== 0) zero_cnt++;
			}
		}
	}
	if (zero_cnt == 0) printf("0\n");
	else printf("%d\n" , check(bfs()));
}