[백준][C++] 16235: 나무 재테크

문제

16235번: 나무 재테크

풀이

구현, 시뮬레이션

 

각 칸을 하나의 구조체로 만들었다. 구조체에는 영양분과 나무를 가지는 vector로 구성된다. 처음에는 sort 작업을 없애기 위해, 우선순위 큐로 만들었지만 오히려 시간초과가 발생하였다. 

struct space
{
	int nutrient = 5;
	vector<int> trees;
};

 

계절 별로 함수로 만들어서 해결한다. 봄, 여름에는 (i, j)위치의 칸의 나무를 오름차순으로 정렬하고, 성장 가능한 나무는 따로 vector에 넣어두고, 성장하지 못 하는 나무는 죽이고, 영양분으로 만든다. 이후 vector에 넣어둔 나무를 다시 해당 칸에 넣는다. 

vector<int> aged_trees;

// 봄
// 나이가 적은 나무부터 성장
sort(ground[i][j].trees.begin(), ground[i][j].trees.end());

int current = 0;
for (; current < ground[i][j].trees.size(); ++current)
{
	int current_tree = ground[i][j].trees[current];

	if (current_tree <= ground[i][j].nutrient)
	{
		ground[i][j].nutrient -= current_tree;
		aged_trees.push_back(current_tree + 1);
	}
	else
	{
		// 현재 나무가 성장할 수 없다면 break;
		break;
	}
}

// 여름
// break된 나무부터 ground에 영양분으로 추가
for (; current < ground[i][j].trees.size(); ++current)
{
	int current_tree = ground[i][j].trees[current];

	ground[i][j].nutrient += (current_tree / 2);
}

// 성장한 나무 ground에 추가
ground[i][j].trees.clear();

for (int aged_tree : aged_trees)
{
	ground[i][j].trees.push_back(aged_tree);
}

 

가을에는 (i, j)칸의 모든 나무를 탐색하며 나이가 5로 나누어 떨어진다면 주위 칸에 나이가 1인 나무를 추가한다. 이 때, 탐색을 진행하면서 나무를 추가한다면, 다음 칸을 탐색할 때, 추가된 나이가 1인 나무도 같이 탐색되므로 시간이 늘어난다. 그러므로 temp_ground를 두어 나무가 추가된 칸을 표시하고 이를 이용하여 나무를 추가한다. 

int temp_ground[10][100] = { 0, };

for (int i = 0; i < N; ++i)
{
	for (int j = 0; j < N; ++j)
	{
		for (int current = 0; current < ground[i][j].trees.size(); ++current)
		{
			int current_tree = ground[i][j].trees[current];

			// 번식 가능하다면 현재 칸 주위의 temp_ground에 1 추가
			if (current_tree % 5 == 0)
			{
				for (int dir = 0; dir < 8; ++dir)
				{
					int next_x = i + move_x[dir];
					int next_y = j + move_y[dir];

					if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N)
					{
						continue;
					}

					temp_ground[next_x][next_y]++;
				}
			}
		}
	}
}

코드

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

using namespace std;

int N, M, K;

struct space
{
	int nutrient = 5;
	vector<int> trees;
};

space ground[10][100];
int A[10][100] = { 0, };
int move_x[8] = { -1, -1, -1,  0,  0,  1,  1,  1 };
int move_y[8] = { -1,  0,  1, -1,  1, -1,  0,  1 };

void spring_summer()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			vector<int> aged_trees;

			// 봄
			// 나이가 적은 나무부터 성장
			sort(ground[i][j].trees.begin(), ground[i][j].trees.end());

			int current = 0;
			for (; current < ground[i][j].trees.size(); ++current)
			{
				int current_tree = ground[i][j].trees[current];

				if (current_tree <= ground[i][j].nutrient)
				{
					ground[i][j].nutrient -= current_tree;
					aged_trees.push_back(current_tree + 1);
				}
				else
				{
					// 현재 나무가 성장할 수 없다면 break;
					break;
				}
			}

			// 여름
			// break된 나무부터 ground에 영양분으로 추가
			for (; current < ground[i][j].trees.size(); ++current)
			{
				int current_tree = ground[i][j].trees[current];

				ground[i][j].nutrient += (current_tree / 2);
			}

			// 성장한 나무 ground에 추가
			ground[i][j].trees.clear();

			for (int aged_tree : aged_trees)
			{
				ground[i][j].trees.push_back(aged_tree);
			}
		}
	}
}

void fall()
{
	int temp_ground[10][100] = { 0, };

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			for (int current = 0; current < ground[i][j].trees.size(); ++current)
			{
				int current_tree = ground[i][j].trees[current];

				// 번식 가능하다면 현재 칸 주위의 temp_ground에 1 추가
				if (current_tree % 5 == 0)
				{
					for (int dir = 0; dir < 8; ++dir)
					{
						int next_x = i + move_x[dir];
						int next_y = j + move_y[dir];

						if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N)
						{
							continue;
						}

						temp_ground[next_x][next_y]++;
					}
				}
			}
		}
	}

	// 번식된 나무 ground에 추가
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			while (temp_ground[i][j] > 0)
			{
				ground[i][j].trees.push_back(1);

				temp_ground[i][j]--;
			}
		}
	}
}

void winter()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			ground[i][j].nutrient += A[i][j];
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> A[i][j];
		}
	}

	for (int i = 0; i < M; ++i)
	{
		int x, y, z;
		cin >> x >> y >> z;

		ground[x - 1][y - 1].trees.push_back(z);
	}

	while (K--)
	{
		spring_summer();
		fall();
		winter();
	}

	int answer = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			answer += ground[i][j].trees.size();
		}
	}

	cout << answer;

	return 0;
}