[BOJ] #16235 _ 나무 재태크

[나무 재테크] https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

시간제한이 0.3초이다.

처음에는 2차원 배열만으로 구현하여 풀이하였으나, 시간 초과가 났다.

시간 복잡도를 잘 생각하여 풀어야 하는 시뮬레이션 문제이다.

 

2차원 배열로 구현하였을 때는 현재 살아있는 모든 나무의 수만큼을 검사하였다.

그러나, 벡터를 사용하여 해당 좌표에 살아있는 나무의 수만큼만 검사하도록 수정하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 11
#define INF 999999999

using namespace std;

int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 }, dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
vector<int> tree[MAX][MAX];
int map[MAX][MAX], A[MAX][MAX];
int N, M, K;

void SpringAndSummer();
void Fall();
void Winter();
int getLiveTree();
int main() {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &A[i][j]);
			map[i][j] = 5;
		}
	}
	while (M--) {
		int y, x, age;
		scanf("%d %d %d", &y, &x, &age);
		tree[y][x].push_back(age);
	}
	
	while (K--) {
		SpringAndSummer();
		Fall();
		Winter();
	}
	printf("%d\n", getLiveTree());

	return 0;
}

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

			sort(tree[i][j].begin(), tree[i][j].end());
			int total = 0, dead_idx = INF;
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] > map[i][j]) {
					total += (tree[i][j][k] / 2);
					dead_idx = min(dead_idx, k);
				}
				else {
					map[i][j] -= tree[i][j][k];
					tree[i][j][k]++;
				}
			}
			if (dead_idx != INF) {
				tree[i][j].erase(tree[i][j].begin() + dead_idx, tree[i][j].end());
				map[i][j] += total;
			}
		}
	}
}

void Fall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < tree[i][j].size(); k++) {
				if (tree[i][j][k] % 5 != 0) continue;
				for (int l = 0; l < 8; l++) {
					int tmp_y = i + dy[l], tmp_x = j + dx[l];

					if (tmp_y < 1 || tmp_x < 1 || tmp_y > N || tmp_x > N) continue;
					tree[tmp_y][tmp_x].push_back(1);
				}
			}
		}
	}
}

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

int getLiveTree() {
	int cnt = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cnt += tree[i][j].size();
		}
	}

	return cnt;
}