[백준] 토마토_7569번

[백준] 토마토

---

문제

링크 : BOJ 익은 토마토가 있을 때, 주변 과일이 하루가 지나면 바로 익는다. 이 때 다 익을 때까지 걸리는 시간을 구한다.

토마토는 M*N 상자가 H 높이만큼 있다.

---

---

풀이

1. 3차원 배열로 map을 선언하자.

2. 토마토가 익을 때 앞뒤상하좌우인 것을 생각해서 방향을 설정하자.

3. 토마토가 모두 익을 때까지 걸리는 최소 시간이므로 현재 상태를 미리 다 받아놔야한다. 그리고 익은 곳에서 각 방향으로 확인하면서 0일 때 모두 1로 바꿔준다.

4. bfs()를 이용하자.

5. 만약 0이 남아있다면, -1을 출력하자.

#include <iostream>
#include <queue>
using namespace std;
int map[100][100][100];
bool visit[100][100][100] = { false };
int dir[6][3] = { {0, 0, -1}, {0,0,1}, {0,1,0},{1,0,0},{0,-1,0}, {-1,0,0} };
int result[100][100][100];
int N, M, H;
int answer = -1;


struct tom
{
	int z; 
	int y; 
	int x;
};
queue<tom> q;
vector<tom> ripe;
void bfs() {
	
	for (int i = 0; i < ripe.size(); i++)
	{
		int x = ripe[i].x;
		int y = ripe[i].y;
		int z = ripe[i].z; 
		q.push({ z, y, x });
		visit[z][y][x] = true;
		result[z][y][x] = 0;
	}
	
	while(!q.empty())
	{
		int c = q.front().z;
		int b = q.front().y;
		int a = q.front().x;
		q.pop();
		for (int i = 0; i < 6; i++)
		{
			int mz = c + dir[i][2];
			int my = b + dir[i][1];
			int mx = a + dir[i][0];
		
			answer = max(result[c][b][a], answer);
			if (mx < 0 || my < 0 || mz < 0 || mx >= M || my >= N || mz >= H)
				continue;

			if (!visit[mz][my][mx] && map[mz][my][mx] == 0)
			{
				map[mz][my][mx] = 1;
				q.push({ mz, my, mx });
				result[mz][my][mx] = result[c][b][a] + 1;
				visit[mz][my][mx] = true;
			}
		}
	}
		
}
int main() {
	ios::sync_with_stdio(false);
	cin.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 >> map[i][j][k];
				if (map[i][j][k] == 1)
					ripe.push_back({ i, j, k });
			}
		}
	}
	bfs();

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

	cout << answer;
	return 0;
}

​

---

실수했던 점

3차원이 아닌 2차원으로 하려했다. 그러니까 맞지 않는 조건들이 생겨나는데 직관적으로 확인할 수 없어서 하루 종일 걸렸다… 3차원이 있을 땐, 겁먹지 말고 일단 해보자.

---