[백준] 7569번. 토마토 (C++)

문제

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

 

해결

3차원 BFS 문제이다.

약간 아리까리해도 침착하게 보면 금방 풀 수 있다!

 

INPUT

토마토 정보를 입력 받는 동시에 익은 토마토는 queue에 넣는다.

 

BFS

queue에서 익은 토마토 위치 정보를 꺼내서 6가지 방향을 모두 확인한다.

vector사이즈에 벗어나지 않고 토마토가 아직 익지 않은 경우만 확인한다.

위의 조건을 모두 만족한다면

now 토마토 값에서 1을 더하여 1일이 지난 것을 표현한다.

box[next[0]][next[1]][next[2]] = box[now[0]][now[1]][now[2]] + 1;

 

CHECK ANSWER

하나라도 익지 않은 토마토가 있다면 -1을 출력한다

그렇지 않으면 box의 최대값-1이 정답 (맨 처음에 익은 토마토 1값에서 하나씩 더해간 것이라)

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

queue<vector<int>>q;
int M, N, H;
const vector<vector<int>> dir = { {1,0,0}, {-1,0,0}, {0,1,0}, {0,-1,0}, {0,0,-1}, {0,0,1} };


int main()
{
	//INPUT
	cin >> M >> N >> H;
	vector<vector<vector<int>>>box(H, vector<vector<int>>(N, vector<int>(M, -1)));
	
	for (int i = 0; i < H; i++)
	{
		for (int k = 0; k < N; k++)
		{
			for (int j = 0; j < M; j++)
			{
				int n;
				cin >> n;
				box[i][k][j] = n;
				if (n == 1) {q.push({ i,k,j });}
			}
		}
	}

	//BFS
	while (!q.empty())
	{
		vector<int> now = q.front();
		q.pop();

		for (int i = 0; i < dir.size(); i++)
		{
			vector<int>next = { now[0] + dir[i][0],now[1] + dir[i][1] ,now[2] + dir[i][2] };

			if (next[0] < 0 || next[1] < 0 || next[2] < 0 || next[0] >= H || next[1] >= N || next[2] >= M) continue;
			if (box[next[0]][next[1]][next[2]] != 0) continue;
			
			box[next[0]][next[1]][next[2]] = box[now[0]][now[1]][now[2]] + 1;
			q.push({ next[0] ,next[1] ,next[2] });
		}
	}
	
	//CHECK ANSWER
	int answer = 0;
	for (int i = 0; i < H; i++)
	{
		for (int k = 0; k < N; k++)
		{
			for (int j = 0; j < M; j++)
			{
				if (box[i][k][j] == 0) { cout << "-1"; return 0; }
				if (box[i][k][j] > answer) { answer = box[i][k][j]; }
			}
		}
	}

	cout << answer - 1; return 0;
}