[BOJ 16235] 나무 재테크 (C++)

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

16235번: 나무 재테크

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct Trees {
	vector<int> list;
};

int N, M, K;
int A[11][11];
int food[11][11];
struct Trees graph[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 springnsummer() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (!graph[i][j].list.empty()) {
				sort(graph[i][j].list.begin(), graph[i][j].list.end());
				int sum = 0;
				for (int k = 0; k< graph[i][j].list.size(); k++) {
					int age = graph[i][j].list[k];
					if (food[i][j] < age) {
						sum += (age / 2);
						graph[i][j].list.erase(graph[i][j].list.begin()+k);
						k--;
					}
					else {
						food[i][j] -= age;
						graph[i][j].list[k] += 1;
					}
				}
				food[i][j] += sum;
			}
		}
	}
}

void fall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (!graph[i][j].list.empty()) {
				for (int age : graph[i][j].list) {
					if (age % 5 == 0) {
						for (int k = 0; k < 8; k++) {
							int nx = i + dx[k]; int ny = j + dy[k];
							if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) {
								graph[nx][ny].list.push_back(1);
							}
						}
					}
				}
			}
		}
	}
}

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

int main() {
	int x, y, z;
	int ans = 0;
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
			food[i][j] = 5;
		}
	}
	for (int i = 0; i < M; i++) {
		cin >> x >> y >> z;
		graph[x][y].list.push_back(z);
	}
	for (int i = 0; i < K; i++) {
		springnsummer();
		fall();
		winter();
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			ans += graph[i][j].list.size();
		}
	}
	cout << ans << "\n";
	return 0;
}

 

구현 문제.

 

자료구조를 어떻게 할 것인가 고민했는데 각 칸=struct trees로 구성하고, struct trees 안의 요소를 vector로 구성하여 여러개의 나무를 담을 수 있도록 했다.

 

age를 비교해서 food보다 작거나 같다면 food를 age만큼 감소시키고, age는 +1 해준다.

food보다 크다면 죽은 나무의 나이/2 를 저장하고 해당 나무를 벡터에서 제거한다. 하나가 감소했으므로 k-- 해줘서 다음 것도 탐색할 수 있도록 한다. 

나무의 갯수는 모든 K년의 계산을 마친 후 배열을 체크해서 구한다.

 

다른 분들 코드를 보니,

deque<int> graph[10][10]; 이런 식으로 자료구조를 해줘서 각 좌표에 deque로 나무들을 담을 수 있도록 한다.

그리고 양분이 적어 먹을 수 없는 나무의 경우일 때,  deque가 빌 때까지 deque에 pop_back() 해주고, back()/2 해줘서 원하는 값을 구한다. 별도로 정렬하지 않고 덱만을 써도 되는 이유는 "입력으로 주어지는 나무의 위치는 모두 서로 다름"의 조건이 있기 때문이다.