BaekJoon 7569 토마토

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

소스결과 5716 KB / 124 ms

출처 Baekjoon, 한국올림피아드 2013 지역본선 초등부 3번

언어 C++ 17 

분류 BFS

 

설명

7576번 토마토의 3차원 버전 문제, 익은 토마토가 상하좌우 뿐만이 아닌 위 아래 칸으로 번지는 경우에 대해서도 계산 해야 하는 문제

 

과거 7576번 토마토 문제를 푼 경험이 있다면 간단한 문제다.

익은 토마토를 기준으로 위칸이나 아래 칸으로 가는 경우를 추가해 주면 된다. 입력의 경우 층수에 맞게 계산 할 수 있게 3차원 배열로 바꿔주어야 한다.

두 조건을 추가하는 모습으로 풀자

 

7576번 토마토 문제 링크 : https://www.acmicpc.net/problem/7569

7576번 토마토 문제 해설 : https://girlfriend-yerin.tistory.com/26

 

소스코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 100;

short box[MAX][MAX][MAX];
bool checkBox[MAX][MAX][MAX];

int posX[6] = { 0, 1 , 0 , -1 , 0, 0 };
int posY[6] = { 0, 0, 1, 0, -1, 0 };
int posZ[6] = { -1, 0, 0, 0, 0, 1 };

struct Point {
	short x;
	short y;
	short z;

	Point(short x, short y, short z) : x(x), y(y), z(z) {}
};

int main()
{
	int row, col, hei;
	int day = -1;
	queue<Point> todayQ;
	queue<Point> tomorrowQ;

	cin >> col >> row >> hei;

	for (int i = 0; i < hei; i++)
	{
		for (int j = 0; j < row; j++)
		{
			for (int k = 0; k < col; k++)
			{
				scanf("%hd", &box[i][j][k]);

				if (box[i][j][k] == 1)
					todayQ.push(Point(j, k, i));
			}
		}
	}

	if (todayQ.empty())
		day = 0;

	while (!todayQ.empty())
	{
		while (!todayQ.empty())
		{
			Point cur = todayQ.front();
			todayQ.pop();

			if (checkBox[cur.z][cur.x][cur.y])
				continue;

			checkBox[cur.z][cur.x][cur.y] = true;

			for (int i = 0; i < 6; i++)
			{
				int nextX = cur.x + posX[i];
				int nextY = cur.y + posY[i];
				int nextZ = cur.z + posZ[i];

				if (0 <= nextX && nextX < row && 0 <= nextY && nextY < col && 0 <= nextZ && nextZ < hei)
				{
					if (box[nextZ][nextX][nextY] == 0 && !checkBox[nextZ][nextX][nextY])
					{
						box[nextZ][nextX][nextY] = 1;
						tomorrowQ.push(Point(nextX, nextY, nextZ));
					}
				}
			}
		}

		while (!tomorrowQ.empty())
		{
			todayQ.push(tomorrowQ.front());
			tomorrowQ.pop();
		}
		day++;
	}

	for (int i = 0; i < hei; i++)
		for (int j = 0; j < row; j++)
			for (int k = 0; k < col; k++)
				if (checkBox[i][j][k] == false && box[i][j][k] != -1)
				{
					cout << -1;
					return 0;
				}

	cout << day;

	return 0;
}