[BOJ]16235번 나무 제태크

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

16235번: 나무 재테크

 

아이디어

1, 나무의 정보를 deque로써 관리를 하고 나이가 적은 나무 쿠터 검사를 진행하기 때문에 나이 순으로 오름차순 정렬을 해 준다.

 

2, 봄 부분에서 나무가 양분을 먹어 살아남는지에 대한 유무와 나이를 먹고 5의 배수가 됐는지 확인하여 각각의 벡터 배열로써 관리를 해 준다.(여름 가을 부분에서 사용)

이 이외에 살아남은 나무는 따로 다시 원래의 나무 deque에 저장하여 관리한다.

 

3, 여름 부분에서 죽은 나무를 관리하는 벡터를 순회하여 양분 정보를 갱신한다.

 

4, 가을 부분에서 새로운 나무를 생성하고 새로운 나무는 항상 나이가 1로써 가장 적은 나이이므로 나무 정보를 담고 있는 deque앞부분에 저장을 하여 오름차순 상태를 유지한다.

 

5, 겨울 부분같은 경우 시간을 절약하기 위해 따로 양분 정보를 저장하는 이차원 배열을 갱신하지는 않았다.

현재 몇년이 지났는지에 대하여만 year변수에 정보를 저장하고 봄 부분에서 양분 정보를 파악할 때 현재의 양분 정보에 매년 더해지는 양분의 양을 고려하여 시간을 절약하였다.

 

#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct tree {
	int r;
	int c;
	int age;
};

deque <tree> trees;
vector<tree> finish;
vector<tree> expansion;

int map[11][11];
int A[11][11];

int N, M, K;

int dr[8] = { 1,0,-1,0,1,1,-1,-1};
int dc[8] = { 0,1,0,-1,1,-1,1,-1 };

int vector_size;
int year = 0;

bool sort_condition(tree a, tree b) {
	if (a.age < b.age) {
		return true;
	}
	else {
		return false;
	}
}

void spring_action() {
	deque<tree> temp_trees;
	vector_size = trees.size();

	for (int i = 0; i < vector_size; i++) {
		tree tree_search = trees[i];
		
		if (map[tree_search.r][tree_search.c] + (A[tree_search.r][tree_search.c] * year) >= tree_search.age) {

			map[tree_search.r][tree_search.c] -= tree_search.age;
			tree_search.age += 1;

			if (tree_search.age % 5 == 0) {
				expansion.push_back(tree_search);
			}

			temp_trees.push_back(tree_search);
		}
		else {
			finish.push_back(tree_search);
		}
	}

	trees = temp_trees;

}

void summer_action() {
	vector_size = finish.size();

	for (int i = 0; i < vector_size; i++) {
		tree tree_search = finish[i];

		map[tree_search.r][tree_search.c] += (tree_search.age/2);
	}

	finish.clear();
}

void autumn_action() {
	vector_size = expansion.size();

	int nr, nc;

	for (int i = 0; i < vector_size; i++) {
		tree tree_search = expansion[i];

		for (int j = 0; j < 8; j++) {
			nr = tree_search.r + dr[j];
			nc = tree_search.c + dc[j];

			if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;

			trees.push_front({ nr,nc,1 });
		}

	}
	expansion.clear();
	
}


int main() {
	int temp_r, temp_c, temp_age;
	scanf("%d %d %d", &N, &M, &K);
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			map[i][j] = 5;
		}
	}

	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &temp_r, &temp_c, &temp_age);

		trees.push_back({ temp_r-1,temp_c-1,temp_age });
	}

	sort(trees.begin(), trees.end(), sort_condition);

	for (int i = 0; i < K; i++) {
		spring_action();
		summer_action();
		autumn_action();
		year++;
	}

	printf("%d\n", trees.size());

	return 0;
}