[BOJ] 7576: 토마토(2차원) 및 7569 데이터 추가 / C++

개요

저번에 회사 동료분이 주신 토마토가 원래 2차원이였지만, 실수로 3차원 문제를 풀어버렸습니다.

그렇기 때문에 2차원도 풀겠다 싶어서 코드를 변경하여 풀었습니다.

풀러가기

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

7576번: 토마토

고민

맞왜틀?

3차원 로직을 2차원 로직으로 변경 한 뒤 제출을 하였는데, 왜인지 틀렸다고 떴습니다.

맞왜틀?

예제입력에 있는 모든 테스트케이스를 입력해보았을때엔 잘 통과가 되었지만, 제출할때엔 문제가 되었습니다.

3차원 배열에서 가능하던 로직이 2차원 배열에서는 안먹히는게 이상했습니다.

중간 과정을 보여주는 테스팅

테스트 케이스를 찾자

문제는 3차원에서는 없지만 2차원 문제에만 있는 테스트 케이스를 찾아 풀어보는것이였습니다.

여러번 테스팅 한 결과 아래의 테스트 케이스가 통과가 되지 않았습니다.

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

 

기댓값은 -1이지만, 결과는 1로 나왔습니다.

위 테스트 결과를 보면, 우측 하단 부분이 채워지지 않았음에도 불구하고 -1이 아닌, 1을 반환하는 문제가 있었습니다.

이를 수정하여 검사내역을 저장하는 Queue가 모두 비워져도, 바로 Day를 반환하지 않도록 수정하였습니다.

 

코드

#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)
{
	cout << "--------------------" << endl;

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

		cout << endl;
	}

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

	for (int i = 0; i < y; ++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 x, int y, int yMax)
{
	bool isHolding = true;

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

	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 (forward >= 0)
		if (tomato[forward][x] != -1) isHolding = false;

	if (back < yMax)
		if (tomato[back][x] != -1) isHolding = false;

	return isHolding;
}

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

	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, 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, Point point, int** tomato, int day, int yMax)
{
	bool hasRipe = false;

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

	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 (forward >= 0 ) //같은층 앞으로
		if (SetDay(day, tomato, Point(point.x, forward))) hasRipe = true;

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

	return hasRipe;
}


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

	int yMax = 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, Point(j, i), tomato, day, yMax))
						{
							noneFind = false;
						}
					}
				}
			}

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

				lastDayQueue.pop();
			}
		}

		lastDayQueue = lastDayQueueTemp;

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

		//DebugTomato(tomato, w, h );

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


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

	int width = 0;
	int height = 0;

	int inputTemp = 0;

	int day = 1;

	int** tomatos;

	cin >> width >> height;

	tomatos = new int* [height * width];

	lastDayQueue = {};

	for (int l = 0; l < height; ++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);
}

3차원 테스트 케이스 추가

그렇다면 전과같은 로직에서 3차원 토마토 문제가 통과되었다는것은, 3차원에는 해당 테스트케이스가 없지 않았을까 하는 의문이 있었습니다.

 

그래서 처음으로 데이터 추가 요청을 올렸습니다.

 

위의 게시물을 올리고 난 뒤에, 며칠 후 3차원 토마토의 재 채점이 완료되었습니다.

마무리

길고 긴 토마토와의 여정이 끝났습니다.

나중에 실력과 여유가 생기면 하이퍼 토마토도 풀 수 있지 않을까요?

17114번: 하이퍼 토마토