[백준/C++] 3차원 토마토

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 토마토의 3차원 버전이다.

 

모든 토마토가 익을 수 있는지 확인하고, 만약 모든 토마토가 익는다면 걸리는 최소 시간을 구하는 문제다.

 

특정위치에 있는 토마토가 익을 수 있는 시간 중 가장 빠른 시간을 구해야 하므로, BFS를 이용하면 첫 방문했을 때가 토마토가 가장 빨리 익는 시간이 되는 것이다.

 

여기서 특정위치에 있는 토마토가 다음으로 탐색할 수 있는 곳은 6방향이다.

이를 이용해 6방향으로 탐색을 하고, 방문한 적이 없으면서 토마토가 있으면 queue에 넣어 탐색을 진행하면 된다.

 

BFS로 문제를 풀 줄 안다면, 처음부터 토마토가 없는 빈칸만 잘 구분해주면 된다.

 

모든 위치에 대해 탐색이 끝났다면, 토마토들을 확인해 안익은 토마토가 있는지 확인하고, 모든 토마토가 익었다면 익는데 가장 오래 걸린 토마토의 시간을 출력하면 된다. 

 

​

[아이디어 정리]

1. 모든 토마토가 익으면서 최소 일수를 확인해야 하므로 BFS로 문제를 푼다.
2. 익은 토마토가 있는 위치를 파악해 queue에 넣는다.
3. 익은 토마토들을 찾았으면, BFS로 탐색을 시작한다.
4. BFS로 탐색이 끝나면, 토마토들을 확인해 모든 토마토가 익었는지 확인하고 정답에 맞는 값을 출력한다.

 

 

 

Code

 

 

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

int dy[6] = {-1, 1, 0, 0,0,0};
int dx[6] = { 0,0,1,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
int tomato[100][100][100];
int visited[100][100][100];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M,H;
	cin >> N >> M>>H;
	queue<vector<int>> q;
	vector<int>nv(3,0);

	for (int i = 0; i < H; i++) 
	{
		for (int j = 0; j < M; j++) 
		{
			for (int k=0; k<N; k++){
				cin >> tomato[i][j][k];
				if (tomato[i][j][k] == 1)
				{
					visited[i][j][k] = 0;
					nv[0] = i, nv[1] = j, nv[2] = k;
					q.push(nv);
				}
				else if (tomato[i][j][k] == -1)
				{
					visited[i][j][k] = 0;
				}
				else 
				{
					visited[i][j][k] = -1;
					tomato[i][j][k] = 0;
				}
			}
		}
	}
	int ny, nx, nz;
	vector<int> temp(3,0);
	while (!q.empty()) 
	{
		nv = q.front();
		q.pop();
		for (int i = 0; i < 6; i++) 
		{
			ny = nv[0] + dy[i];
			nx = nv[1] + dx[i];
			nz = nv[2] + dz[i];
			if (ny >= 0 && ny < H && nx >= 0 && nx < M && nz>=0&& nz<N&&tomato[ny][nx][nz] == 0)
			{
				visited[ny][nx][nz] = visited[nv[0]][nv[1]][nv[2]] + 1;
				tomato[ny][nx][nz] = 1;
				temp[0] = ny, temp[1] = nx, temp[2] = nz;
				q.push(temp);
			}
		}
	}
	int maxDay = 0;
	for (int i = 0; i < H; i++) 
	{
		for (int j = 0; j < M; j++) 
		{
			for (int k = 0; k < N; k++) 
			{
				if (visited[i][j][k] == -1)
				{
					cout << -1;
					cin >> M;

					return 0;
				}
				maxDay = max(maxDay, visited[i][j][k]);
			}
		}
	}
	cout << maxDay;
	return 0;
}

 

---

3차원 BFS도 단지 방향이 많을 뿐 똑같이 풀 수 있는 문제라 어렵지 않다.

 

7569번: 토마토