[백준 C++] 7569 토마토 - 너비우선탐색

7569번: 토마토

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

typedef tuple<int, int, int> Coord;

int Box[100][100][100];
int Day[100][100][100];

int M, N, H;
int DX[6] = { -1, 1, 0, 0, 0, 0 }; // Left, Right
int DY[6] = { 0, 0, -1, 1, 0, 0 }; // Top, Bottom
int DZ[6] = { 0, 0, 0, 0, -1, 1 }; // Down, Up

queue<Coord> SearchQueue;

int CountDays()
{
	int MaxDay = 0;
	
	// Binary First Search
	while (!SearchQueue.empty())
	{
		int X = get<0>(SearchQueue.front());
		int Y = get<1>(SearchQueue.front());
		int Z = get<2>(SearchQueue.front());
		SearchQueue.pop();

		if (Box[Z][Y][X] == -1)
		{
			continue;
		}

		Box[Z][Y][X] = -1;
		for (int i = 0; i < 6; ++i)
		{
			int NX = X + DX[i];
			int NY = Y + DY[i];
			int NZ = Z + DZ[i];

			if (NX < 0 || NX > M - 1
				|| NY < 0 || NY > N - 1
				|| NZ < 0 || NZ > H - 1
				|| Box[NZ][NY][NX] == -1)
			{
				continue;
			}

			if (Box[NZ][NY][NX] == 0)
			{
				Box[NZ][NY][NX] = 1;

				int NewDay = Day[Z][Y][X] + 1;
				Day[NZ][NY][NX] = NewDay;
				if (NewDay > MaxDay)
				{
					MaxDay = NewDay;
				}
			}

			SearchQueue.emplace(NX, NY, NZ);
		}
	}

	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			for (int k = 0; k < M; ++k)
			{
				if (Box[i][j][k] == 0)
				{
					return -1;
				}
			}
		}
	}

	return MaxDay;
}

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

	cin >> M >> N >> H;

	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			for (int k = 0; k < M; ++k)
			{
				cin >> Box[i][j][k];
				if (Box[i][j][k] == 1)
				{
					SearchQueue.emplace(k, j, i);
				}
			}
		}
	}

	cout << CountDays();
}

---

 

3차원 공간에서 너비 우선 탐색을 이용해서 푸는 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 입력 받은 토마토 정보 box 배열에 저장 - 처음부터 익은 토마토는 BFS 큐에 추가

2. 각 토마토가 몇번째 날에 익었는지 정보를 담는 day 배열 모두 0 값으로 초기화

3. 큐에 담긴 토마토부터 너비 우선 탐색 시작

4. 익지 않은 인접 토마토에 현재 토마토 날짜 + 1 날짜 값 저장 - 이 때 현재까지 증가된 날짜 중 최대값은 따로 저장

5. 탐색을 마친 후, 저장해놓은 날짜 최대값 출력 - 예외처리: 익지 않은 토마토가 존재하면 -1 출력