[BOJ] 7569: 토마토 / C++

개요

회사 동료분께서 소개시켜준 3차원 토마토입니다.

그래프, BFS관련문제라고 나와있는데 너무 어거지로 푼게 아닌가 생각듭니다.

풀러가기

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

7569번: 토마토

고민

속도 제한 고민

원래 아래의 코드 처럼 순회를 다 돌렸습니다.

그런데 속도 제한이 걸려서 고민을 했습니다.

for (int i = 0; i < yMax; ++i)
{
  for (int j = 0; j < w; ++j)
  {
    if (tomato[i][j] == day - 1)
    {
      if (Find(w, h, f, Point(j, i), tomato, day, yMax))
      {
      	noneFind = false;
      }
    }
  }
}

 

그런데 생각해보니 처음 순회가 끝나면 확장한 위치 기준들로 검사를 돌리면 되지 않을까?라는 생각이 들었습니다.

그래서 마지막으로 넓혀주었던 위치를 queue에 넣어서 저장시켰습니다.

while (!lastDayQueue.empty())
{
  if (Find(w, h, f, lastDayQueue.front(), tomato, day, yMax))
  	noneFind = false;

  lastDayQueue.pop();
}

확장한 위치들을 queue에 넣었으니, 두번째날 부터는 큐에 있는 위치들만 돌려보니 시간 초과 이슈가 해결되었습니다.

틀렸습니다 까지는 갔다!!!

테스트 케이스 고민

백준에 있는 테스트 케이스는 다 성공인데 틀림으로 나왔어서 당황했습니다.

아래 테스트 케이스를 돌려보니 -1이 아닌 0이 나왔습니다.

 

2 3 2
1 -1
-1 0 
-1 -1
1 -1
-1 0 
-1 -1

 

해당 이슈를 해결하니 맞았습니다.

좋네요

코드

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

using namespace std;

struct Point
{
public:
	int x = 0;
	int y = 0;

	Point(int _x, int _y)
	{
		x = _x;
		y = _y;
	}
};
queue<Point> lastDayQueue;
queue<Point> lastDayQueueTemp;

void DebugTomato(int** tomato, int x, int y, int h)
{
	cout << "--------------------" << endl;

	for (int i = 0; i < y * h; ++i)
	{
		for (int j = 0; j < x; ++j)
		{
			cout << tomato[i][j];
		}

		cout << endl;
	}

	cout << "--------------------" << endl;
}
bool NotRipe(int** tomato, int x, int y, int h)
{
	bool hasNotRipe = false;

	for (int i = 0; i < y * h; ++i)
	{
		for (int j = 0; j < x; ++j)
		{
			if (tomato[i][j] == 0)
				hasNotRipe = true;
		}
	}

	return hasNotRipe;
}

bool CheckHold(int** tomato, int w, int h, int f, int x, int y, int yMax)
{
	bool isHolding = true;

	int left = x - 1;
	int right = x + 1;

	int downY = y - h;
	int upY = y + h;

	int forward = y - 1;
	int back = y + 1;

	if (right < w)
		if (tomato[y][right] != -1) isHolding = false;

	if (left >= 0)
		if (tomato[y][left] != -1) isHolding = false;

	if (upY < yMax) //한 층 위
		if (tomato[upY][x] != -1) isHolding = false;
	if (downY >= 0) //한 층 아래
		if (tomato[downY][x] != -1) isHolding = false;

	if (forward >= 0 && (forward % h != (h - 1))) //같은층 앞으로
		if (tomato[forward][x] != -1) isHolding = false;

	if (back < yMax && (back % h != 0)) //같은층 뒤로
		if (tomato[back][x] != -1) isHolding = false;

	return isHolding;
}

bool IsHold(int** tomato, int w, int h, int f)
{
	bool isHold = false;
	int yMax = h * f;

	bool notTomatoCase = true;

	for (int y = 0; y < yMax; ++y)
	{
		for (int x = 0; x < w; ++x)
		{
			if (tomato[y][x] == 0)
			{
				if (CheckHold(tomato, w, h, f, x, y, yMax))
					return true;
			}
			if (tomato[y][x] != -1)
				notTomatoCase = false;
		}
	}

	if (notTomatoCase)
		return true;

	return isHold;
}

bool SetDay(int day, int** tomato, Point point)
{
	if (tomato[point.y][point.x] == 0)
	{
		tomato[point.y][point.x] = day;
		lastDayQueueTemp.push(point);
		return true;
	}
	if (tomato[point.y][point.x] == day)
		return false;

	if (tomato[point.y][point.x] == -1)
		return false;

	return false;
}


//만약 하나라도 익히지 못했다면 false
bool Find(int w, int h, int f, Point point, int** tomato, int day, int yMax)
{
	bool hasRipe = false;

	int left = point.x - 1;
	int right = point.x + 1;

	int downY = point.y - h;
	int upY = point.y + h;

	int forward = point.y - 1;
	int back = point.y + 1;

	if (right < w)
		if (SetDay(day, tomato, Point(right, point.y))) hasRipe = true;

	if (left >= 0)
		if (SetDay(day, tomato, Point(left, point.y))) hasRipe = true;

	if (upY < yMax) //한 층 위
		if (SetDay(day, tomato, Point(point.x, upY))) hasRipe = true;
	if (downY >= 0) //한 층 아래
		if (SetDay(day, tomato, Point(point.x, downY))) hasRipe = true;

	if (forward >= 0 && (forward % h != (h - 1))) //같은층 앞으로
		if (SetDay(day, tomato, Point(point.x, forward))) hasRipe = true;

	if (back < yMax && (back % h != 0)) //같은층 뒤로
		if (SetDay(day, tomato, Point(point.x, back))) hasRipe = true;

	return hasRipe;
}


int AddDay(int& day, int** tomato, int w, int h, int f)
{
	if (IsHold(tomato, w, h, f))
	{
		return -1;
	}
	int yMax = f * h;

	while (true)
	{
		++day;

		bool noneFind = true;

		if (lastDayQueue.empty()) //처음 파악할 때 사용
		{
			for (int i = 0; i < yMax; ++i)
			{
				for (int j = 0; j < w; ++j)
				{
					if (tomato[i][j] == day - 1)
					{
						if (Find(w, h, f, Point(j, i), tomato, day, yMax))
						{
							noneFind = false;
						}
					}
				}
			}

			if (noneFind)
			{
				if (NotRipe(tomato, w, h, f))
				{
					return -1;
				}
			}
		}
		else
		{
			while (!lastDayQueue.empty())
			{
				if (Find(w, h, f, lastDayQueue.front(), tomato, day, yMax))
					noneFind = false;

				lastDayQueue.pop();
			}
		}

		lastDayQueue = lastDayQueueTemp;

		while (!lastDayQueueTemp.empty())
		{
			lastDayQueueTemp.pop();
		}

		//DebugTomato(tomato, w, h, f);

		if (noneFind)
		{
			if (NotRipe(tomato, w, h, f))
			{
				return -1;
			}
			return day - 2;
		}
	}
}


int main()
{
	ios_base::sync_with_stdio(false);

	int width = 0;
	int height = 0;

	int floor = 0;

	int inputTemp = 0;

	int day = 1;

	int** tomatos;

	cin >> width >> height >> floor;

	tomatos = new int* [height * floor];

	lastDayQueue = {};

	for (int l = 0; l < height * floor; ++l)
	{
		tomatos[l] = new int[width];
		for (int w = 0; w < width; ++w)
		{
			cin >> inputTemp;
			tomatos[l][w] = inputTemp;
		}
	}

	cout << AddDay(day, tomatos, width, height, floor);
}