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

 

<코드>

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

int map[101][101][101];
int dx[6] = { 1,-1,0,0,0,0 };
int dy[6] = { 0,0,1,-1,0,0 };
int dh[6] = { 0,0,0,0,1,-1 };
int N, M, H; // 세로,가로,높이
int day = 1;
bool tomato = true;
queue<tuple<int, int, int>> q;

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

	cin >> M >> N >> H;

	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= M; k++)
			{
				cin >> map[i][j][k];
				if (map[i][j][k] == 1)
					q.push(make_tuple(i, j, k));
			}

	// BFS
	while (!q.empty())
	{
		int now_h = get<0>(q.front());
		int now_x = get<1>(q.front());
		int now_y = get<2>(q.front());

		q.pop();

		for (int i = 0; i < 6; i++)
		{
			int next_h = now_h + dh[i];
			int next_x = now_x + dx[i];
			int next_y = now_y + dy[i];

			if (next_x >= 1 && next_y >= 1 && next_h >= 1)
				if (next_x <= N && next_y <= M && next_h <= H)
				{
					if (map[next_h][next_x][next_y] == 0)
					{
						map[next_h][next_x][next_y] = map[now_h][now_x][now_y] + 1;
						day = max(day, map[next_h][next_x][next_y]);
						q.push(make_tuple(next_h, next_x, next_y));
					}
				}
		}
	}

	/*
	cout << "map 결과 출력" << endl;
	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int k = 1; k <= M; k++)
			{
				cout << map[i][j][k] << " ";
			}
			cout << endl;
		}
	}
	*/
	

	// 안익은 토마토가 있는지 확인
	for (int i = 1; i <= H; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int k = 1; k <= M; k++)
			{
				if (map[i][j][k] == 0)
				{
					tomato = false;
					break;
				}
			}
			if (tomato == false) break;
		}
		if (tomato == false) break;
	}


	if (tomato) cout << day - 1;
	else cout << -1;
}

 

예제 출력

 

 

www.acmicpc.net/problem/7569

7569번: 토마토