[문제풀이] 백준 16235번 나무 재테크

백준 16235번 나무 재테크

문제 해설

특정 알고리즘을 사용해 푸는 문제는 아니고 시뮬레이션 문제다.

따라서 문제가 제시한 대로 구현을 하면 되는 것이지만, 중요한 것은 시간이 0.3초밖에 되지 않아 자료구조를 잘 쓰는 것이 중요하다.

처음엔 우선순위 큐를 사용해 풀었지만, push 연산이 O(logN)이다보니 시간초과가 났다.

이를 해결하기 위해 push,pop를 빠르게 할 수 있는 deque 자료구조를 사용하였다.

1. 입력
총 10*10까지 가능하니 각 칸에서 자라는 나무를 deque tree[11][11]에 저장한다. 다만 deque의 경우 정렬이 되지 않으므로 vector를 통해 입력받아 sort해준 다음에 deque에 넣어주었다.

2. 계절

봄 :
- 각 칸의 deque의 나무를 pop하면서 해당 칸의 양분보다 나이가 적은지 비교한다.
- 양분이 나이보다 크다면 양분에서 나이를 빼주고 new_deque에 나이+1를 해준다. 나이가 더 크다면 2로 나누어 죽은 나무에 속하게 된다.
- new_deque에는 나이+1 된 나무만 존재한다. new_deque을 해당 칸의 deque으로 할당한다.
여름 :
- 봄에서 죽은 나무들의 값을 양분으로 추가한다.
가을:
- 각 칸의 deque을 돌면서 나이가 5의 배수라면 주변 칸의 deque front에 나이가 1인 나무를 추가한다. 나이 1이 제일 어리므로 front에 추가한다.
겨울 :
- 양분에 A[r][c]추가

3. 계산
모든 칸이 동시에 봄을 맞이하고 그 후 여름, 가을, 겨울 순으로 맞이하게 된다.
따라서 각 칸마다 한 계절씩 끝내고 다음 계절을 넘어가야 한다.

소스코드

#include <iostream>
#include <vector>
#include <deque>
#include <utility>
#include <algorithm>

 // 백준 16235번 나무 재테크

using namespace std;

// 0. 나이 어린 나무부터 양분 먹으므로 나이 어린 나무가 앞으로 와야 한다. => 우선순위 큐(시간 초과) => 덱의 앞 뒤 이용.
// 0-0. 위치별 나무 저장한 후, 정렬해서 덱에 저장.
// 1. 봄/여름 : 덱 돌면서 양분 먹고 나이 1 증가. 양분 못먹으면 dead에 나이/2 추가. 
// 2. 가을/겨울 : 나이 확인해서 주변 나무 심기
// 3. K번 반복.
// 4. 전체 나무 돌면서 덱의 사이즈 확인.


int n, m, k;
int A[11][11];
int map[11][11];
vector<int> temp[11][11];
deque<int> tree[11][11];
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };

// 봄, 여름
void ss(int r, int c) {
	deque<int> d = tree[r][c];
	deque<int> newTree;
	int dead = 0;
	while (!d.empty()) {
		int t = d.front();
		d.pop_front();

		if (t <= map[r][c]) {
			map[r][c] -= t;
			newTree.push_back(t + 1);
		}
		else {
			dead += t / 2;
		}
	}
	map[r][c] += dead;
	tree[r][c] = newTree;
	return;
}
// 가을, 겨울
void fw(int r, int c) {
	deque<int> d = tree[r][c];
	while (!d.empty()) {
		int t = d.front();
		d.pop_front();
		if (t % 5 == 0) {
			for (int i = 0; i < 8; i++) {
				int nx = r + dx[i];
				int ny = c + dy[i];
				if (nx > 0 && nx <= n && ny>0 && ny<=n) {
					tree[nx][ny].push_front(1);
				}
			}
		}
	}
	map[r][c] += A[r][c];
	
	return;
}
// 초기 나무 나이별 정렬하여 덱에 저장.
void push() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			sort(temp[i][j].begin(), temp[i][j].end());
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < temp[i][j].size(); k++) {
				tree[i][j].push_back(temp[i][j][k]);
			}
		}
	}
}
int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> A[i][j];
	
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		temp[x][y].push_back(z);
	}
	// 정렬
	push();

	// map 초기화
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			map[i][j] = 5;
	
	// k년
	while (k--) {
		// 모든 칸마다 봄,여름
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) 
				ss(i, j);
		// 가을, 겨울
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				fw(i, j);
	}
	int answer = 0;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			answer += tree[i][j].size();

	cout << answer;
	

	return 0;
}