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

•  문제

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

7569번: 토마토

• 풀이법 ( 알고리즘 )

7576번 토마토에서 축을 하나 추가해 풀 수 있다.

Queue를 선언할 때 <pair <pair <int, int>, pair <int, int>>> 형식으로 선언하여 각각에 높이 인덱스, 현재 토마토가 익는데 걸린 날짜, 가로 인덱스, 세로 인덱스를 저장해주었다.

• 풀이 - C++

#include <iostream>
#include <queue>

using namespace std;

int M, N, H, cnt = 0;
int tomato[120][120][120];
int visit[121][121][121];

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 main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	queue <pair<pair<int,int> , pair<int,int>>> Q; // {{h , cnt} , {x , y}}

	//input
	cin >> M >> N >> H;

	for (int h = 0; h < H; h++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin >> tomato[h][i][j];
				if (tomato[h][i][j] == 1)
					Q.push({ {h,cnt}, {i,j} });
			}
		}
	}

	//solve
	int x, y, h;
	while (!Q.empty())
	{
		x = Q.front().second.first;
		y = Q.front().second.second;
		cnt = Q.front().first.second;
		h = Q.front().first.first;
		Q.pop();

		for (int i = 0; i < 6; i++) 
		{
			int dX = x + dx[i];
			int dY = y + dy[i];
			int dH = h + dh[i];

			if (dX < 0 || dX >= N || dY < 0 || dY >= M || dH >= H || dH < 0 || visit[dH][dX][dY] == 1 ) continue;
			if (tomato[dH][dX][dY] == 0)
			{
				Q.push({ {dH,cnt + 1},{dX,dY} });
				visit[dH][dX][dY] = 1;
				tomato[dH][dX][dY] = 1;
			}
		}

		
	}
	
	//output
	for (int h = 0; h < H; h++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (tomato[h][i][j] == 0)
				{
					cout << "-1";
					return 0;
				}
			}
		}
	}

	cout << cnt;
	return 0;
}