백준 16235번 나무 재테크

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

16235번: 나무 재테크

 

 

 

 

<접근방법>

시뮬레이션 문제입니다.

풀면서 자료구조 선택이 승패를 좌우하겠구나 생각했습니다.

 

나무에 대한 정보, 현재 양분에 대한 정보,  뿌리는 양분에 대한 정보, 죽은 나무에 대한 정보를

보관해야합니다.

 

나무에 대한 정보의 경우, 나무가 여러 개 겹칠 수 있고, 얼마나 겹칠지 알 수가 없습니다.

그래서 이차원 배열 벡터로 구현하였습니다.

현재 양분, 뿌리는 양분에 대한 정보는 이차원 배열로 하였습니다.

죽은 나무의 상태는 좌표마다 달라집니다. 그래서 초기화만 신경써주면 뭘 해도 상관없습니다.

보통 큐나 매개변수 사용이 초기화에 대한 걱정을 없애줍니다.

 

나무의 이차원 배열 벡터에서 죽은 나무를 빼는 것을 갯수 카운팅으로 처리하였습니다.

구현하면서도 너무 위험한 방법이라고 생각했으나, 급한 마음에 그냥 했습니다.

다른 분 코드를 보니 살아남은 친구들을 임시의 공간에 저장하고

해당 좌표의 나무 공간을 싹 비운 다음, 살아남은 친구들만 넣어주었습니다.

왜 이 생각을 못했을까...

구현이 힘들거나 위험하면 메모리를 더 쓸 생각을 해보자!

 

 

---

 

 

 

<코드>

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

struct info {
	int y, x, age;
};

int n, m, k;
int lunch[10][10], map[10][10];
int dy[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};

vector<int> tree[10][10];
queue<info> die;

int cal() {
	int res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			res += tree[i][j].size();
		}
	}
	return res;
}

void spring() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int sz = tree[i][j].size();
			if (sz == 0) continue;
			sort(tree[i][j].begin(), tree[i][j].end());

			int alive = 0;
			for (int u = 0; u < sz; u++) {

				int t = tree[i][j][u];
				if (map[i][j] >= t) {
					map[i][j] -= t;
					tree[i][j][u]++;
					alive++;
				}
				else {
					die.push({i, j, t});
				}
			}
			tree[i][j].erase(tree[i][j].begin() + alive, tree[i][j].end());
		}
	}
}

void summer() {
	while (!die.empty()) {
		info t = die.front();
		die.pop();

		map[t.y][t.x] += (t.age/2);
	}
}

void fall() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int u = 0; u < tree[i][j].size(); u++) {
				if (tree[i][j][u] % 5 == 0) {
					for (int d = 0; d < 8; d++) {
						int ty = i + dy[d];
						int tx = j + dx[d];

						if (ty < 0 || ty >= n || tx < 0 || tx >= n) continue;
						tree[ty][tx].push_back(1);
					}
				}
			}
		}
	}
}

void winter() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			map[i][j] += lunch[i][j];
		}
	}
}

void simul() {
	while (k--) {
		//봄
		spring();
		//여름
		summer();
		//가을
		fall();
		//겨울
		winter();
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lunch[i][j];
			map[i][j] += 5;
		}
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> b >> a >> c;
		b--; a--;
		tree[b][a].push_back(c);
	}

	simul();
	cout << cal() << '\n';
	return 0;
}

 

 

---

 

 

<느낀 점>

-구현이 힘들거나 위험하면 메모리를 더 쓸 생각을 해보자!