BOJ 7569 - 토마토

해당 문제는 3차원 그래프 순회 + multi source 처리에 대한 문제이다.

이전 실버 단계에서 풀었던 grid 형태의 그래프 순회에 3차원의 높이 축까지 확장한 형태이며 

본질은 크게 다르지 않다.

 

처음 방문 노드 -> 다음 간선 이동 -> 중복 방문 방지 예외 처리 

 

해당 3가지 틀을 의식하여 문제를 정의해 본다.

 

처음 방문 노드

익은 토마토를 1, 안익은 토마토를 0, 토마토가 없는 위치를 -1로 설정하였을 때,

처음 queue에 넣어야 할 요소들은 익은 토마토의 위치들이다.

중요한 것은 익은 토마토들이 하루가 지날수록 동시에 단계씩 퍼져 나가기 때문에

한번에 input으로 넣어 처리 해 주어야 한다. 

 

이를 multi source(여러개의 출발점)에 관련된 문제라고 하는 것 같다.

multi source는 이밖에도 이후 dijkstra 등에서도 다루어지는 문제인 듯 하다.

 

다음 간선 이동

다음 이동이 가능한 간선은 

앞, 뒤 좌, 우, 위, 아래 총 6방향이다. 

이를  dx, dy, dz 전역 배열을 통해 다음 간선으로 이동할 로직을 처리한다.

다음 간선으로 이동했을 때 먼저 판단해야 하는 것은 해당 노드가 out of range인지를 판단하는 것이다. 

 

중복 방문 방지 예외 처리 

해당 문제에서 처리하고자 하는 것은 안익은 토마토를 단계별로 익은 토마토로 바꾸면서 해당 단계의 날짜를 세는 것이다. 

즉, 0을 1로 바꾸고, 다음노드에서 토마토가 이미 익은 상태라면 queue에 넣지 않도록 처리한다. 

 

한편, 여기서 메모리 최적화를 해 볼 수 있는데, 토마토를 0에서 1로 바꾸는 처리에서 그냥 한번에 

날짜를 세도록 하는 것이다.

예를 들어 0 0 1 순서로 있다면 

쉽게 생각할 수 있는 방법은  1 1 1 로 단계별로 처리하고 따로 날짜 배열을 두어서 2 1 0 으로 계산하는 것이지만

어짜피 토마토가 익었는지 안익었는지에 대한 상태만 중요하기 때문에 

0 0 1 을 3 2 1 로 처리하여 0이 아니라면 이미 익은 상태일 것이고 0이면 아직 순회하지 않은 상태이므로

두마리 토끼를 다 잡을 수 있다.

 

대신, 해당 방법은 원본 데이터를 훼손하는 방식이라 찝찝하지만 ps에서는 최적화를 위해서 이와 같은 처리를 자주 사용한다고 하니 익숙해 지도록 하자. 

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int m,n,h;

	cin>>m>>n>>h;

	vector<vector<vector<int>>> tomatobox(h, vector<vector<int>>(n,vector<int>(m)));
	queue<tuple<int,int,int>> q;

	for(int z=0; z<h; z++)
	{
		for(int y=0; y<n; y++)
		{
			for(int x =0; x<m; x++)
			{
				cin>>tomatobox[z][y][x];
				//토마토가 익은 위치를 queue에 저장
				if(tomatobox[z][y][x] ==1)
					q.push({z,y,x});
			}
		}
	}

	while(!q.empty())
	{
		//현재 위치 
		//structured binding 문법
		auto [curz,cury,curx] = q.front();
		q.pop();

		for(int i = 0; i<6; i++)
		{
			int nextz = curz + dz[i];
			int nexty = cury + dy[i];
			int nextx = curx + dx[i];

			if(nextz <0 || nextz >=h || nexty <0 || nexty >=n || nextx <0 || nextx >=m) continue;
			if(tomatobox[nextz][nexty][nextx] !=0 ) continue; //비어있거나 이미 익은거면 패스
			
			//날짜를 그냥 해당 데이터에 저장하기 -> 데이터 훼손 but 메모리 절약
			tomatobox[nextz][nexty][nextx] = tomatobox[curz][cury][curx] + 1;
			q.push({nextz, nexty, nextx});
		}
	}

	bool ripen = true;
	int max = 0;

	for(int z =0; z<h; z++)
	{
		for(int y = 0; y<n; y++)
		{
			for(int x = 0; x<m; x++)
			{
				if(tomatobox[z][y][x] == 0)
				{
					ripen = false;
				}
				if(max< tomatobox[z][y][x]) max = tomatobox[z][y][x];
			}
		}
	}
	
	if(!ripen) cout<<-1<<"\n";

	else
	{
		// 처음 익은 상태는 0일로 세므로 -1
		cout<<max-1<<"\n";
	}
}