BOJ 7569 : 토마토

BOJ 7569

[BOJ 7569 (S1) 토마토 리뷰]

 

토마토 2D버전을 푼 경험이 있기에 쉽게 풀었다.

기존 4방향에서 확인하던것을 '상,하,좌,우,위,아래' 6가지 경우에 대해 BFS를 수행하면된다.

한가지 생각해야 할점은 익은 토마토가 여러개 존재할 수 있으므로 시작할때 존재하는 익은 토마토 모두에 대해 BFS를 수행해야 한다. 이는 익은 토마토를 미리 Q에 push함으로써 해결할 수 있다. 1일에 1칸씩 이동할 수 있기에 BFS를 수행할때마다 현재위치+1를 해주면 가장 거리값이 큰 위치가 마지막으로 토마토가 익는 위치이다.

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

#define X first
#define Y second
int board[102][102][102];
int dist[102][102][102];
int dx[6] = { 1,0,-1,0,0,0};
int dy[6] = { 0,1,0,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(0);
	queue <tuple<int, int, int>> Q;
	int n, m, h;
	cin >> m >> n >> h;
	for (int k = 0; k < h; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				cin >> board[i][j][k];
				if (board[i][j][k] == 0)
					dist[i][j][k] = -1;
				if (board[i][j][k] == 1)
					Q.push({ i,j,k });
			}
		}
	}
	while (!Q.empty())
	{
		auto cur = Q.front();
		Q.pop();
		for (int dir = 0; dir < 6; dir++)
		{
			int curx = get<0>(cur);
			int cury = get<1>(cur);
			int curz = get<2>(cur);
			int nx = curx + dx[dir];
			int ny = cury + dy[dir];
			int nz = curz + dz[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h) continue;
			if (dist[nx][ny][nz] != -1 || board[nx][ny][nz]!=0) continue;
			dist[nx][ny][nz] = dist[curx][cury][curz] + 1;
			Q.push({ nx,ny,nz });
		}
	}
	
	int ans = 0;
	for (int k = 0; k < h; k++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (dist[i][j][k] == -1)
				{
					cout << -1;
					return 0;
				}
				ans=max(ans, dist[i][j][k]);
			}
		}
	}
	
	cout << ans;
	
}