백준 BOJ 16235 C++ 나무 재테크 (삼성 기출)

[문제 링크]

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

16235번: 나무 재테크

 

[문제 풀이]

전형적인 삼성 시뮬레이션 기출문제이다.

문제에서 봄, 여름, 가을, 겨울에 하는 일을 정의해놨기 때문에 본인은 4개의 함수를 구현했다.

함수를 보기 전에 선언한 변수를 살펴보겠다.

MAP은 해당 자리에 있는 양분의 양이다. 양분은 처음에 모든 자리에 5가 있다.

eat은 겨울에 해당 자리에 추가되는 양분의 양이다.

tree는 해당 자리에 있는 나무들의 나이를 담는 배열이다. 여러 개의 나무가 같은 자리에 있을 수 있기 때문에 덱 배열을 사용하였다.

여기서 덱을 사용한 이유는 나무를 쉽게 푸시하고 팝 하기 위해서이다.

dead_tree는 해당 자리에서 죽은 나무이다. 마찬가지로 해당 자리에 죽은 나무가 여러 개 있을 수 있기 때문에 벡터 배열로 선언하였다.

그리고 가을에서 인접한 8자리에 번식하는 것을 구현하기 위해 dx, dy 배열을 사용하였다.

이 문제에서 가장 애먹은 부분은 봄 부분이었다.

봄의 조건에서 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다고 되어 있다.

이 조건 때문에 tree 배열을 덱으로 선언하였다. 덱을 사용하면 가장 어린 나무를 바로 뽑을 수 있기 때문이다.

본인은 모든 자리를 탐색하면서 해당 자리에 나무의 크기만큼 반복문을 수행했다.

여기서 미리 해당 자리의 나무 개수를 구하고 나무 개수만큼 반복문을 돌린 이유는 반복문 안에서 푸시와 팝이 이루어지는데 미리 정해준 나무 개수만큼 돌리지 않으면 우리가 원하는 대로 결과가 나오지 않기 때문이다.

예를 들어 (0,0) 자리에 나이가 1인 나무가 3개 있고 양분은 7이라고 가정해보자.

여기서는 당연히 나무의 개수인 3번만큼만 반복문이 돌아야 한다.

그렇지 않다면 나이가 1이었던 나무들은 해당 자리에 양분이 충분하지 않을 때까지 나이를 먹을 것이다.

마지막 조건을 보면 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 즉시 죽는다고 하였다.

이 말이 처음에는 조금 헷갈렸는데 말을 바꿔보면 현재 나무의 나이보다 해당 자리의 양분이 더 작다면 나무는 죽는 것이다.

이때 죽은 나무는 dead_tree 배열에 넣어줬다.

봄 부분만 해결하면 나머지 부분은 어렵지 않게 구현할 수 있다.

여름에서는 해당 자리에 죽은 나무가 있다면 그 죽은 나무의 나이를 2로 나눈 값을 해당 자리의 양분에다가 추가하면 된다.

가을에서는 나무의 나이가 5의 배수이면 인접한 8칸에 나이가 1인 나무를 추가한다.

여기서 tree 배열을 덱으로 선언한 이유가 나온다.

나이가 1인 나무라는 것은 결국 가장 어린 나무를 뜻한다. 그렇기 때문에 나무가 번식을 한다면 해당하는 자리 맨 앞에 1을 푸시해준다.

겨울은 가장 간단하다.

해당하는 자리에 처음에 입력받았던 양분을 추가해주면 된다.

이 작업을 K번 반복했을 때 남아있는 나무의 수를 구하는 문제이다.

K번 반복하고 난 후에 모든 자리를 탐색하면서 해당하는 자리의 사이즈를 더해주었다.

[소스 코드]

#include <bits/stdc++.h>
using namespace std;
int n, m, K;
int MAP[11][11];
int eat[11][11];
deque<int> tree[11][11];
vector<int> dead_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 spring() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int size = tree[i][j].size();
			while (size--) {
				int age = tree[i][j].front();
				tree[i][j].pop_front();
				if (MAP[i][j] < age) {
					dead_tree[i][j].push_back(age);
					continue;
				}
				MAP[i][j] -= age;
				tree[i][j].push_back(age + 1);
			}
		}
	}
}

void summer() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int size = dead_tree[i][j].size();
			while (size--) {
				int age = dead_tree[i][j].back();
				dead_tree[i][j].pop_back();
				MAP[i][j] += (age / 2);

			}
		}
	}
}

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++) {
				int age = tree[i][j][k];
				if (age % 5 == 0) {
					for (int dir = 0; dir < 8; dir++) {
						int nx = i + dx[dir];
						int ny = j + dy[dir];
						if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
						tree[nx][ny].push_front(1);
					}
				}
			}
		}
	}
}

void winter() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			MAP[i][j] += eat[i][j];
		}
	}
}

void count_tree() {
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			sum += tree[i][j].size();
		}
	}
	cout << sum;
}
void INPUT() {
	cin >> n >> m >> K;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			MAP[i][j] = 5;
			cin >> eat[i][j];
		}
	}

	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		tree[x][y].push_back(z);
	}
}

void solve() {
	while (K--) {
		spring();
		summer();
		fall();
		winter();
	}
	count_tree();
}
void solution() {
	INPUT();
	solve();
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	solution();
	return 0;
}