16235 나무 재테크

www.acmicpc.net/problem/16235

16235번: 나무 재테크

문제의 조건들을 잘 지켜서 구현하는 시뮬레이션 문제이다.

이 문제에서 예제 8이 77이 나와서 고생했었는데, 이 경우 가을에 번식되는 나무가 하나가 아니라는 것만 유의하여 구현하면 해결된다!

이제 문제를 살펴보자. 얼핏 보면 나이가 어린 나무부터 정렬해야 할 것 같은 느낌인데, 정렬 없이 구현할 수 있다.

1. 문제의 조건 중에 입력으로 주어지는 나무엔 겹치는 경우가 없다.

2. 나이가 어린 나무부터 순차적으로 양분을 먹는다.

3. 더 이상 먹을 양분이 없으면 그 뒤부터는 죽은 나무이다.

4. 가을엔 나이가 1인 나무가 번식한다.

이 동작은 덱(deque)으로 비슷하게 구현할 수 있다.

조건 4는 맨 앞에 1인 원소를 넣으면 되고, 죽은 나무들은 pop_back을 하면 되기 때문이다.

정답코드

/*
예제 8이 77이 나오는 경우, 가을에 나무가 '한 번만' 번식하는건 아닌지 확인해보자
*/
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int N, M, K;
int A[11][11];
deque<int> live_tree[11][11];
deque<int> dead_tree[11][11];
int arr[11][11];
int dirRow[] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int dirCol[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void spring()
{
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			auto& t = live_tree[r][c];
			auto& d = dead_tree[r][c];
			int size = t.size();
			for (int i = 0; i < size; i++) {
				int age = t.front();
				t.pop_front();
				if (arr[r][c] >= age) {
					arr[r][c] -= age;
					t.push_back(age + 1);
				}
				else {
					d.push_back(age);
				}
			}
		}
	}
}
void summer()
{
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			auto& d = dead_tree[r][c];
			int size = d.size(), age;
			for (int i = 0; i < size; i++) {
				age = d.front();
				arr[r][c] += age / 2;
				d.pop_front();
			}
		}
	}
}
void fall()
{
	int nr, nc;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			auto& t = live_tree[r][c];
			int size = t.size();
			for (int k = 0; k < size; k++) {
				if (t[k] % 5 == 0) {
					for (int i = 0; i < 8; i++) {
						nr = r + dirRow[i];
						nc = c + dirCol[i];
						if (nr < 1 || nc < 1 || nr > N || nc > N)
							continue;
						auto& nt = live_tree[nr][nc];
						nt.push_front(1);
					}
				}
			}
		}
	}
}
void winter()
{
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			arr[r][c] += A[r][c];
		}
	}
}
int main()
{
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &A[i][j]);
			arr[i][j] = 5;
		}
	}
	int x, y, z;
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d", &x, &y, &z);
		auto &t = live_tree[x][y];
		t.push_back(z);
	}
	while (K--) {
		spring();
		summer();
		fall();
		winter();
	}
	int answer = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			auto&t = live_tree[r][c];
			answer += t.size();
		}
	}
	printf("%d\n", answer);
	return 0;
}