[알고리즘] 토마토(7569)

구현 방식

• 이전에 풀던 토마토 2D 를 3D로 변경
• 튜플 말고, 구조체 Pos 생성

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>

using namespace std;

struct Pos
{
	Pos(int z, int y, int x)
	{
		this->z = z;
		this->y = y;
		this->x = x;
	}
	int z;
	int y;
	int x;
};

void solution(int H, int N, int M);
void bfs(int H, int N, int M);
bool canRipen(Pos& nextPos, int H, int N, int M);

int graph[101][101][101];
queue<Pos> q;

int main()
{
	int N, M, H;
	cin >> M >> N >> H;
	int empties = 0;
	for (int z = 0; z < H; z++)
		for (int y = 0; y < N; y++)
			for (int x = 0; x < M; x++)
			{
				cin >> graph[z][y][x];
				if(graph[z][y][x] == 1) q.push({ z, y, x});
				else if (graph[z][y][x] == -1) empties++;
			}

	int unRipenTomatoes = N * M * H - q.size() - empties;
	if (unRipenTomatoes == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	solution(H,N, M);
}


void solution(int H, int N, int M )
{
	bfs(H, N, M);

	int result = INT_MIN;
	for (int z = 0; z < H; z++)
		for (int y = 0; y < N; y++)
			for (int x = 0; x < M; x++)
			{
				if (graph[z][y][x] == 0)
				{
					cout << -1;
					return;
				}
				result = max(graph[z][y][x], result);

			}

	cout << result - 1;
}

void bfs(int H, int N, int M)
{
	Pos surround[6] = { {-1, 0, 0},{1, 0,0},
						{0, -1, 0},{0, 1,0},
						{0,0,-1},{0,0,1} };

	while (!q.empty())
	{
		Pos currPos = q.front();
		q.pop();
		for (auto& surr : surround)
		{
			Pos nextPos = { currPos.z + surr.z ,currPos.y + surr.y ,currPos.x + surr.x };
			if (canRipen(nextPos, H, N , M))
			{
				graph[nextPos.z][nextPos.y][nextPos.x] = graph[currPos.z][currPos.y][currPos.x] + 1;
				q.push(nextPos);
			}
		}

	}

}


bool canRipen(Pos& nextPos, int H , int N, int M)
{
	if (nextPos.z < 0 || H <= nextPos.z)
		return false;
	if (nextPos.y < 0 || N <= nextPos.y)
		return false;
	if (nextPos.x < 0 || M <= nextPos.x)
		return false;
	if (graph[nextPos.z][nextPos.y][nextPos.x] == -1)
		return false;
	if (graph[nextPos.z][nextPos.y][nextPos.x] == 0)
		return true;
	return false;
}