[백준] 7569번 토마토 (C++)

문제

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

M * N * H로 이루어진 박스에 토마토들이 담겨 있는데, 익은 토마토가 되기 위해서는 안 익은 토마토 근처에 익은 토마토가 있을 때, 하루가 지나면 익은 토마토가 된다.

 

박스에 모든 토마토가 익은 토마토가 될려면 며칠이 지나야하는지 출력하는 문제이다.

 

입력 조건은 -1(토마토가 없는 박스), 0(안익은 토마토), 1(익은 토마토)이다.

풀이

3차원 배열에 박스 정보를 입력받고, 익은 토마토 좌표를 큐에 저장한 뒤, BFS를 이용하여 날짜를 계산했다.

 

큐가 비었을 때 BFS가 끝나므로 출력할 땐, count - 1를 한다.

#include <bits/stdc++.h>

using namespace std;

int dx[6] = {0, 0, 1, -1,0,0 };
int dz[6] = {1, -1, 0, 0,0,0};
int dy[6] = {0, 0 , 0 , 0 , 1, -1};
int n, m, h;
int arr[100][100][100];
queue<pair<pair<int,int>, int>> q;

void BFS()
{
	int count = 0;
	while (!q.empty())
	{
		int size = q.size();
		for(int k = 0; k < size; k++)
		{
			int x = q.front().first.second, z = q.front().first.first,  y = q.front().second;
			q.pop();

			for(int i = 0; i < 6; i++)
			{
				int moveX = x + dx[i], moveZ = z + dz[i], moveY = y + dy[i];
				if(moveX < 0 || moveX >= m || moveZ < 0 || moveZ >= n || moveY < 0 || moveY >= h) continue;

				if(arr[moveZ][moveX][moveY] == 0)
				{
					arr[moveZ][moveX][moveY] = 1;
					q.push({{moveZ, moveX}, moveY});
				}
			}
		}
		count ++;
	}

	for(int k = 0; k < h; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
			{
				if(arr[i][j][k] == 0)
				{
					cout << -1;
					return;
				}
			}

	cout << count - 1;
}

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

	cin >> m >> n >> h;

	bool b = false;
	for(int k = 0; k < h; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
			{
				cin >> arr[i][j][k];

				if(arr[i][j][k] == 0)
					b = true;
				else if(arr[i][j][k] == 1)
					q.push({{i, j}, k});
			}

	if(!b)
		cout << 0;
	else
		BFS();
		
	return 0;
}