[알고리즘] C++ 백준 7569 토마도

 

백준 7569

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

7569번: 토마토

 

풀이 전 나의 생각

다른 토마토 문제는 2차원 BFS였는데 뭔가 똑같은 이름의 토마토 문제가 하나 더 있어서 클릭해 봤다.

비슷하긴 한데 축이 하나 더 늘었다. 여기서 굉장히 헷갈렸는데 보통 2차원 배열만 사용하지 3차원 까지는 거의

사용하지 않기 때문이다. 그래서 이 문제를 풀려면 우선 3차원 배열의 개념부터 잡고가야 한다.

C++의 3차원 배열은 arr[z][x][y], z부터 시작한다.

 

이해를 돕기 위해 그림을 보면 z 값이 토마토가 여러개 쌓여 있는 높이를 나타내고

x와 y는 토마토가 쌓여질 판을 의미한다.

 

그래서 삼중 for문을 사용하여 z, x, y를 순서대로 값을 받으면 된다.

요약하자면 z의 높이에 x, y크기의 판이라고 생각하면 편하다.

 

그리고 기존대로 BFS를 진행하면 되는데

한 가지 더 생각해야 될거는 최종적으로는 다 익을 경우의 날짜를 구해야 한다는 것이다.

이를 구하기 위해서 양방향 위, 아래를 탐색을 진행할 때 마다 익지 않은 토마토의 위치로 이동할 때  현재 위치의 방문 값에  + 1을 더해주면서 방문 값을 채워나가면 된다.

 

1. 방문한 위치의 값을 다루는 visit배열에 익은 토마토 1, 덜익은 토마토 -1 값을 넣어준다.

2. BFS에서 처음 탐색할 때 시작 값은 익은 토마토인 1부터 시작하기 때문에 이를 1일이라고 가정한다.

3. 탐색을 진행한 후 익지 않은 토마토의 다음 위치를 찾았다면 현재 진행중인 익은 토마토의 1일 값에 + 1을 해준다.

4. 그러면 다음 토마토의 방문한 위치 값은 2가 되며 2일 째에 익어졌다는 의미가 된다.

5. 반복한다.

 

->  모든 탐색이 끝난 후 visit배열의 최대값을 구한다면 그것이 최종 결과 값 (1일부터 시작했기 때문에 최종 결과 값에 -1을 빼준다)이 될 것이고

만약 토마토가 익지않은 -1값이 여전히 있다면 -1을 출력하며 종료해준다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>

using namespace std;
int board[102][102][102];
int visit[102][102][102];

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

queue<pair<pair<int, int>, int>> q;
int n, m, h = 0;

void BFS()
{
	while (!q.empty())
	{
		int z = q.front().first.first;
		int x = q.front().first.second;
		int y = q.front().second;

		q.pop();
		for (int i = 0; i < 6; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nz = z + dz[i];

			if (nx < 0 || ny < 0 || nz < 0 || nx >= n || ny >= m || nz >= h) continue;
			if (visit[nz][nx][ny] == -1 && board[nz][nx][ny] == 0)
			{
				visit[nz][nx][ny] = visit[z][x][y] + 1;
				q.push({ { nz, nx }, ny });
			}			
		}
	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int day = 0;
	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 >> board[i][j][k];

				if (board[i][j][k] == 1)
				{
					q.push({ {i, j} , k });
					visit[i][j][k] = 1;
				}
				else if (board[i][j][k] == 0)
				{
					visit[i][j][k] = -1;
				}
			}
		}
	}

	BFS();

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < m; k++)
			{
				if (visit[i][j][k] == -1 && board[i][j][k] == 0)
				{
					cout << -1;
					return 0;
				}

				day = max(day, visit[i][j][k]);
			}
		}
	}
	cout << day - 1;
}