[백준/BOJ] 백준 7569번 : 토마토

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

7569번: 토마토

익은 토마토의 위치에서 왼쪽, 오른쪽, 뒤쪽, 앞쪽, 위쪽, 아래쪽 방향으로 bfs 하며 익지 않은 토마토가 있을 때 익은 토마토로 바꾼다. bfs를 진행하면서 깊이는 날짜가 증가할 때마다 증가하므로 bfs가 끝났을 때 가장 깊은 깊이가 토마토가 모두 익을 때까지 걸린 최소일수이다.

 

코드

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

vector<pair<pair<int, int>, int>> growed;
int box[100][100][100];
int dx_dy[6][3] = { {0,-1,0}, {0,1,0}, {-1,0,0}, {1,0,0},{0,0,1},{0,0,-1} };
int m, n, h;
bool discovered[100][100][100];
int depth[100][100][100];

//박스에 익지 않은 토마토가 있는지 확인한다
bool checkBox()
{
	bool ret = true;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < h; k++)
			{
				if (box[i][j][k] == 0)
					return false;
			}

	return ret;
}

//discoverd초기화
void discoveredMake()
{
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100; j++)
			for (int k = 0; k < 100; k++)
				discovered[i][j][k] = false;
}

//익어있는 토마토에서 bfs를 통해 다른 토마토가 모두 익을때 까지의 최소 날짜를 출력한다
int solve()
{

	int day = 0;
	queue<pair<pair<int, int>, int>> q;

	discoveredMake();

	//익어있는 토마토들의 위치를 시작으로 왼쪽, 오른쪽, 뒤쪽, 앞쪽, 위쪽, 아래쪽 방향으로 bfs를 시작한다
	for (int i = 0; i < growed.size(); i++)
	{
		//익어있는 토마토들의 발견 표시를 한다
		discovered[growed[i].first.first][growed[i].first.second][growed[i].second] = true;

		//bfs의 시작이므로 깊이를 0으로 한다
		depth[growed[i].first.first][growed[i].first.second][growed[i].second] = 0;

		//큐에 익어있는 토마토들의 위치를 넣는다
		q.push(growed[i]);
	}

	//큐에 무언가 있다면 탐색을 진행한다
	while (!q.empty())
	{
		pair<pair<int, int>,int> here = q.front();
		q.pop();
		
		//탐색하는 위치는 익은 토마토가 된다
		box[here.first.first][here.first.second][here.second] = 1;

		//왼쪽, 오른쪽, 뒤쪽, 앞쪽, 위쪽, 아래쪽 방향으로 탐색을 진행한다
		//단 탐색은 탐색을 진행할 위치가 box의 범위를 벗어나지 않아야 하고, 해당 위치에 익지 않은 토마토가 있어야 하고, 해당위치가 아직 발견되지 않았어야 한다
		for (int i = 0; i < 6; i++)
		{
			pair<pair<int, int>, int> there = make_pair(make_pair(here.first.first + dx_dy[i][0], here.first.second + dx_dy[i][1]), here.second + dx_dy[i][2]);
			
			if (there.first.first >= 0 && there.first.first < n && there.first.second >=0 && there.first.second < m && there.second >= 0 && there.second < h && box[there.first.first][there.first.second][there.second]==0 && discovered[there.first.first][there.first.second][there.second] == false)
			{
				//해당위치를 발견했다고 표시
				discovered[there.first.first][there.first.second][there.second] = true;

				//해당 위치의 깊이는 here의 깊이 + 1이다
				depth[there.first.first][there.first.second][there.second] = depth[here.first.first][here.first.second][here.second] + 1;

				//day는 가장 깊은 깊이이다(계속 업데이트 한다)
				day = max(day, depth[there.first.first][there.first.second][there.second]);

				//나중에 탐색할 위치 이므로 큐에 넣는다
				q.push(make_pair(make_pair(there.first.first, there.first.second),there.second));
			}
		}
	}

	//박스에 익지 않은 토마토가 있을때
	if (checkBox() == false)
		return -1;

	return day;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp;

	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 >> temp;
				box[i][j][k] = temp;

				//익은 토마토의 위치일때
				if (temp == 1)
					growed.push_back(make_pair(make_pair(i, j), k));
			}
	
	cout << solve();

	return 0;
}