백준 7569번: 토마토 (C++)

문제 링크 : www.acmicpc.net/problem/7569

 

 

배열을 전부 탐색해나가며 토마토를 익게 하면 당연히 시간초과가 난다.

이 문제는 bfs로 간단히 해결할 수 있다. 

 

bfs 알고리즘  : wlshddlek.tistory.com/8?category=883327

 

 

<전체적인 알고리즘>

1. bfs로 토마토를 익게하며 제일 늦게까지 탐색되는 토마토가 몇일만에 탐색되었는지 구한다.

2. 토마토다 다익었으면 제일 늦게 익은 토마토 day를 반환,  안익은게 있으면 -1반환

 

 

*bfs로 탐색을 할 때 queue안의 각 점에서 모두 탐색을 한다는 것을 이용한다

 -> 시작점을 여러개 넣어도 각 시작점에서 모두 탐색해 나감.

 

 

 

 

<전체 코드>

#include<iostream>
#include<queue>

using namespace std;

class ins
{
public:
	int x, y, z, day;
	ins(int x, int y , int z, int day)
	{
		this->x = x;
		this->y = y;
		this->z = z;
		this->day = day;
	}
};

int dir[6][3] = { {-1,0,0},{0,1,0},{1,0,0},{0,-1,0},{0,0,1},{0,0,-1} };
int m, n,h;
int box[102][102][102];
queue<ins> q;


bool all_ripe()   // 다익었는지 확인
{
	for (int z = 0; z < h; z++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (box[i][j][z] == 0)
				{
					return false;
				}
			}
		}
	}
	return true;
}

int spread()   //사과 익는거 퍼뜨리기
{
	int max_day = 0;
	while (!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().z;
		int day = q.front().day;

		q.pop();
		max_day = day;

		for (int d = 0; d < 6; d++)
		{
			int nextx = x + dir[d][0];
			int nexty = y + dir[d][1];
			int nextz = z + dir[d][2];
			
			if (nextx < 0 || nexty < 0 || nextz < 0 || nextx >= n || nexty >= m || nextz >= h)continue;
			if (box[nextx][nexty][nextz] == 0)
			{
				q.push(ins(nextx, nexty, nextz, day + 1));
				box[nextx][nexty][nextz] = 1;
			}
		}
	}
	return max_day;
}

int main()
{
	cin >> m >> n>>h;

	for (int z = 0; z < h; z++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				int num;
				cin >> num;
				box[i][j][z] = num;
				if (num == 1)q.push(ins(i, j, z, 0));
				
			}
		}
	}
	int total_day=spread();  //익는데 제일 오래걸린 토마토 날짜 반환

	if (all_ripe())cout << total_day;  //다익었으면 
	else cout << "-1";   //안익은게 있으면 

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.