BaekJoon: 7569번 토마토(C++)

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

7569번: 토마토

풀이법

1) BFS를 활용하여 최단거리를 찾는 문제이다.

2) x,y,z를 둘 때 값이 헷갈릴 수 있으니 이 부분을 조심해야 한다.

필자의 경우 아래와 같은 방식으로 x,y,z 값을 두었다.

(0,0,0) (0,1,0) (0,2,0)

(1,0,0) (1,1,0) (1,2,0)

3) tomato 배열 내에 0이 남아있는지 확인하는 별도의 함수를 활용하여 익지 못한 토마토를 찾았다.

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

int n, m, k;
int vx[6] = { 1,0,-1,0,0,0 };
int vy[6] = { 0,1,0,-1,0,0 };
int vz[6] = { 0,0,0,0,1,-1 };
bool visited[101][101][101];
int arr[101][101][101];
int ans = 0;
bool show()
{
	for (int t = 0; t < k; t++)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (arr[i][j][t] == 0)
					return false;

			}
		}
	}
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n >> k;// x : n y:m z:k
	queue<pair<int, pair<int, pair<int, int>>>> q;
	for (int t = 0; t < k; t++)
		for (int i = 0; i < n; i++) //x
			for (int j = 0; j < m; j++) //y
			{
				cin >> arr[i][j][t];
				if (arr[i][j][t] == 1)
				{
					visited[i][j][t] = true;
					q.push({ i,{j,{t,0}} });
				}
			}



	while (!q.empty())
	{
		int tx = q.front().first;
		int ty = q.front().second.first;
		int tz = q.front().second.second.first;
		int cnt = q.front().second.second.second;
		q.pop();
		ans = max(ans, cnt);
		for (int i = 0; i < 6; i++)
		{
			int bx = tx + vx[i];
			int by = ty + vy[i];
			int bz = tz + vz[i];
			if (bx<0 || by<0 || bz<0 || bx>=n || by>=m || bz>=k)
				continue;
			if (arr[bx][by][bz] == 0 && !visited[bx][by][bz])
			{
				visited[bx][by][bz] = true;
				arr[bx][by][bz] = 1;
				q.push({ bx,{by,{bz,cnt + 1}} });
			}
		}
	}
	bool chk = show();
	if (chk == true)
		cout << ans;
	else
		cout << -1;


}
	

최종 값인 ans는 현재까지 나온 cnt 중 가장 큰 값으로 두었다. 실제로 BFS 알고리즘 특성 상 queue에 값을 넣기 위해서는 아래의 조건을 만족해야 한다.

			if (bx<0 || by<0 || bz<0 || bx>=n || by>=m || bz>=k)
				continue;
			if (arr[bx][by][bz] == 0 && !visited[bx][by][bz])
			{
				visited[bx][by][bz] = true;
				arr[bx][by][bz] = 1;
				q.push({ bx,{by,{bz,cnt + 1}} });
			}

아직 익지 않은 토마토가 들어갔을 때만 cnt+1이 되기에 queue가 empty가 되어 빠져나왔을 때, 마지막으로 익은 것의 날짜 수를 확인하면 되는 문제이므로, 최대 cnt 값을 찾아 문제를 해결했다.