[백준/BOJ] 백준 16235번 : 나무 재테크

www.acmicpc.net/problem/16235

16235번: 나무 재테크

봄, 여름, 가을, 겨울 때마다 하는 연산을 설정해 놓고 k번 반복한다. 각 칸의 나무의 정보는 deque<int> tree[11][11]를 통해 저장해 놓는다. 각 해마다 죽은 나무는 vector<pair<int, pair<int, int>>> dead_tree를 통해 저장해 놓고 사용한다(죽은 나무의 나이와, 위치 저장) 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>
using namespace std;

int n, m, k;
int board[11][11];
int a[11][11];
int dxdy[8][2] = { {0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };
deque<int> tree[11][11];

int Solve()
{
	int ret = 0;

	//k년을 센다
	for (int year = 0; year < k; year++)
	{
		vector<pair<int, pair<int, int>>> dead_tree; //죽은 나무의 나이와, 위치 저장

		//봄
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				for (int kk = 0; kk < tree[i][j].size(); kk++)
				{
					if (tree[i][j][kk] <= board[i][j]) //양분을 먹을 수 있을때
					{
						board[i][j] -= tree[i][j][kk]; //양분을 먹는다
						tree[i][j][kk] += 1; //나이가 1 증가
					}

					else //양분을 먹을 수 없을때 해당 나무의 나이 이상의 나무들은 모두 죽게 된다
					{
						for (int l = kk; l < tree[i][j].size(); l++)
							dead_tree.push_back(make_pair(tree[i][j][l], make_pair(i, j))); //죽은 나무의 나이와, 위치 저장

						tree[i][j].erase(tree[i][j].begin() + kk, tree[i][j].end()); //나무 정보에서 죽은 나무들 삭제

						break;
					}
				}
			}
		}

		//여름
		for (int i = 0; i < dead_tree.size(); i++)
			board[dead_tree[i].second.first][dead_tree[i].second.second] += (dead_tree[i].first / 2);

		//가을
		vector<pair<int, int>> maked_site; //새로운 나무가 만들어지는(번식하는) 칸
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				for (int kk = 0; kk < tree[i][j].size(); kk++)
				{
					if (tree[i][j][kk] % 5 == 0) //나무의 나이가 5의 배수일때
					{
						for (int l = 0; l < 8; l++)
						{
							pair<int, int> seed_site = make_pair(i + dxdy[l][0], j + dxdy[l][1]);

							if (seed_site.first >= 1 && seed_site.first <= n && seed_site.second >= 1 && seed_site.second <= n)
								maked_site.push_back(seed_site);
						}
					}
				}
			}
		}

		for (int i = 0; i < maked_site.size(); i++)
			tree[maked_site[i].first][maked_site[i].second].push_front(1); //나이가 1인 나무가 생긴다

		//겨울
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				board[i][j] += a[i][j];
	}

	//나무의 개수를 센다
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			ret += tree[i][j].size();

	return ret;
}

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

	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			a[i][j] = input;
			board[i][j] = 5; //가장 처음 양분은 모든칸에 5만큼 있다
		}
	}

	//나무의 정보
	for (int i = 0; i < m; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;

		tree[x][y].push_back(z);
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			if (!tree[i][j].empty())
				sort(tree[i][j].begin(), tree[i][j].end()); //나이가 어린 나무 순으로 정렬
		}

	cout << Solve();

	return 0;
}