[백준 7569] 토마토

문제설명

토마토가 상자안에 들어있다 

가로M, 세로N, 높이 H로 상자가 주어진다

1은 토마토가 익어있다는 의미이고, -1은 빈 공간이다.

하루마다 익은 토마토를 기점으로 위,아래, 상,하,좌,우가 익는다

모든 토마토가 다 익는데 걸리는 최소한의 기간을 출력시킨다

단, 토마토가 원래 다 익어있는 경우에는 0을 출력하고, 토마토가 다 익지 못하는 경우는 -1을 출력시킨다

알고리즘

1. 입력 정보 받기 

2. 그래프의 값이 1인(토마토가 익은경우) queue에 그 좌표값을 넣는다

3. bfs알고리즘을 사용하여 상,하,좌,우, 위, 아래를 모두 확인한다

4. 방문기록을 조회하여 0이 남아있는 경우 -1을 출력하고 그렇지 않은  경우엔 최대값을 출력시킨다

코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int N, M, H;

int graph[101][101][101];
int visited[101][101][101];
queue<pair<int, int>>q;
queue<int> h;
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 };
void bfs() {
	
	while (!q.empty()) {

		int x = q.front().first;
		int y = q.front().second;
		int height = h.front();

		q.pop();
		h.pop();

		for (int i = 0; i < 6; i++)
		{
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			int nh = dh[i] + height; //높이도 받기 

			if (nx<0 || ny<0 || nx>=N || ny>=M ||nh<0 || nh>=H)
				continue;

			if (graph[nh][nx][ny] == 0 && visited[nh][nx][ny] == 0) {
				q.push({ nx,ny });
				h.push(nh);
				visited[nh][nx][ny] = visited[height][x][y] + 1;
			}
		}
		
	}
	
}
int main() {

	cin >> M >> N >> H ;

	for (int k = 0; k < H; k++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin >> graph[k][i][j];
				if (graph[k][i][j] == 1) //토마토가 익은 경우 담아놓기 
				{
					q.push({ i,j });
					h.push(k);
				}
			}
		}
	}
	

	bfs();
	int max = 0;
	for (int k = 0; k < H; k++)
	{
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (visited[k][i][j] > max)
					max = visited[k][i][j];//걸린 일 수 계산
				if (visited[k][i][j] == 0 && graph[k][i][j] == 0)//토마토가 안익은 경우 
				{
					cout << -1;
					return 0;
				}
			}
		}
	}
	cout << max;
	return 0;
}

고찰

이 문제는 전에 푼 내용에 3차원으로 바뀐 것만 추가되었다

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

7576번: 토마토

방식과 알고리즘은 동일한데 처음에 3차원이여서 당황스러웠다

하지만 3차원으로  배열을 받고, 그대로 진행하면되는데 대신 조회할 방향이 6개로 늘어났다

전의 문제 풀이 방식은 아래와 같다

https://gyeong99.tistory.com/search/%ED%86%A0%EB%A7%88%ED%86%A0