[BOJ7569][C++] 토마토

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

7569번: 토마토

 

문제

전형적인 bfs문제인데 이차원배열에서 층이 더해진 삼차원배열에서 생각하는 문제이다.

 

해결

🎈Key Point🎈

기존의 전형적인 bfs 해결풀이에서 배열을 삼차원으로 선언한 뒤 풀어나가면 된다.

그리고 맨처음 익어있는 토마토에서 -> 하루 뒤 익은 토마토 -> 이틀 뒤 익은 토마토 -> .. 를 계산해야하므로

거리 배열을 하나 더 선언하여

아직 익지 않은 토마토의 거리를 -1로 설정하고 (가장 처음에 익어있는 토마토는 0으로 설정된 상태)

bfs를 실행하여 토마토가 익으면 bfs를 실행했던 지점의 토마토의 거리에서 1을 더한 값으로 새로 익은 토마토의 거리 값을 업데이트한다.

최종적으로 거리 값들 중 최대값이 정답이 된다.

 

[전체 코드]

#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>

int m, n, h;	// 가로(x), 세로(y), 높이(h)
int board[100][100][100];
int dis[100][100][100];		// 거리 이용
queue<tuple<int, int, int>> Q;
int dx[6] = { -1,1,0,0,0,0 };
int dy[6] = { 0,0,-1,1,0,0 };
int dz[6] = { 0,0,0,0,-1,1 };
int result = 0;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n >> h;
	for (int i = 0; i < h; i++)	{	// z
		for (int j = 0; j < n; j++)	{	// y
			for (int k = 0; k < m; k++) {	// x
				int tom;
				cin >> tom;		// 1: 익은, 0: 익지 않은, -1: 없음
				board[k][j][i] = tom;
				if (tom == 1) Q.push({ k,j,i });
				if (tom == 0) dis[k][j][i] = -1;
			}
		}
	}

	while (!Q.empty()) {
		auto tomato = Q.front(); Q.pop();
		int tomX, tomY, tomZ;
		tie(tomX, tomY, tomZ) = tomato;
		
		for (int i = 0; i < 6; i++) {
			int nx = tomX + dx[i];
			int ny = tomY + dy[i];
			int nz = tomZ + dz[i];

			if (nx < 0 || nx >= m || ny < 0 || ny >= n || nz < 0 || nz >= h) continue;
			if (dis[nx][ny][nz] != -1) continue;	// 익을 토마토가 아닌 이미 익은 토마토거나/빈 칸이라면
			dis[nx][ny][nz] = dis[tomX][tomY][tomZ] + 1;	// 하루 더하기
			Q.push({ nx, ny, nz });
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < h; k++) {
				if (dis[i][j][k] == -1) {	// 익지 않은 토마토가 있으면
					cout << -1;
					return 0;
				}
				result = max(result, dis[i][j][k]);
			}
		}
	}
	cout << result;
	return 0;
}