[BOJ] 16235 : 나무 재테크 - travelbeeee

문제 : https://www.acmicpc.net/problem/16235

---

[ 알고리즘풀이 ]

curMap[x][y] : 현재 (x, y) 지점의 양분

dead[x][y] : (x, y) 지점에 봄에 죽은 나무들의 양분

A[x][y] : (x, y) 지점에 겨울에 추가될 양분

tree[x][y] : (x, y) 지점에 존재하는 나무들의 나이 ( 더 좋은 자료구조가 생각이 안나서, 각 지점마다 vector 배열을 만들어 현재 그 지점에 존재하는 나무들의 나이를 저장했습니다. )

 

1. Spring

각 지점마다 나무가 존재한다면, 나무들의 나이를 sort해서 어린 나무부터 양분을 줍니다. 이때, 양분이 부족한 나무들을 count 해주고, 나이 순으로 sort가 된 상태고, 어린 나무부터 양분을 주므로 count 만큼 pop_back 을 진행하면 죽은 나무들을 vector 에서 제외할 수 있습니다. 또, 나무가 죽었다면 dead 에 나이 / 2 만큼 양분을 추가해줍니다.

 

2. Summer

각 지점마다 curMap[x][y] += dead[x][y] 를 진행하고, dead[x][y] = 0 (초기화) 를 진행합니다.

 

3. Fall

각 지점마다 나무가 존재한다면, 나무들의 나이를 순회하며 나이가 5의 배수인 나무가 있다면 주변에 나무를 추가해줍니다.

 

4. Winter

각 지점마다 curMap[x][y] += A[x][y] 를 진행해줍니다.

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

using namespace std;

int N, M, K, curMap[11][11] = {}, dead[11][11] = {}, A[11][11] = {}, x, y, z;
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
vector<int> tree[11][11] = {};

void spring(void) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tree[i][j].empty())
				continue;

			int deadTree = 0;
			sort(tree[i][j].begin(), tree[i][j].end());
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] <= curMap[i][j]) {
					curMap[i][j] -= tree[i][j][k];
					tree[i][j][k] += 1;
				}
				else {
					dead[i][j] += tree[i][j][k] / 2;
					deadTree++;
				}
			}
			for (int k = 0; k < deadTree; k++)
				tree[i][j].pop_back();
		}
	}
}

void summer(void) {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++){
			curMap[i][j] += dead[i][j];
			dead[i][j] = 0;
		}
}

void fall(void) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (tree[i][j].empty())
				continue;
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] % 5 == 0) {
					for (int l = 0; l < 8; l++) {
						int x = i + dx[l], y = j + dy[l];
						if (1 <= x && x <= N && 1 <= y && y <= N)
							tree[x][y].push_back(1);
					}
				}
			}
		}
	}
}

void winter(void) {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			curMap[i][j] += A[i][j];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++){
			cin >> A[i][j];
			curMap[i][j] = 5;
		}

	for (int i = 1; i <= M; i++) {
		cin >> x >> y >> z;
		tree[x][y].push_back(z);
	}
		
	while (K--){
		spring();
		summer();
		fall();
		winter();
	}

	int ans = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			ans += tree[i][j].size();
	cout << ans;
}

---