백준 16235번: 나무 재테크

[문제 링크]

16235번: 나무 재테크

---

문제를 풀기에 앞서 땅을 표현하는 Land 클래스와 로봇을 표현하는 Robot 클래스를 설계하였다.

 

로봇은 땅에 양분을 공급하는 역할을 수행한다. 따라서 Robot 클래스의 supplyNutrients() 메서드에서 Land 객체의 레퍼런스 타입을 매개변수로 받아 Land 클래스의 increaseNutrients() 메서드를 호출하여 땅에 양분을 공급하도록 설계하였다. 

Robot 클래스의 메서드에서 Land 클래스를 매개변수로 받는 형태를 이루고 있기 때문에 이 둘은 서로 연관 관계임을 알 수 있다. 따라서 연관 관계를 뜻하는 점선 화살표로 두 클래스를 연결하였다.

 

알고리즘은 다음과 같다.

1. N, M, K를 입력 받는다. 그다음 Land Size 값을 N으로 초기화한 Land 객체와 Robot 객체를 생성한다.

2. H2D2가 땅에 공급하는 양분을 배열로 입력 받아 설정한다.

3. 문제에서 요구하는 대로 봄, 여름, 가을, 겨울에 나타나는 일들을 그대로 구현한다.

4. 봄->여름->가을->겨울 순으로 함수를 호출한다. 그리고 이를 K번 반복한다.

5. K번 반복한 후 땅에 심어진 나무의 개수를 출력한다.

 

// 봄에 나무가 양분을 흡수하는 과정에서 나이가 어린 나무부터 양분을 먹도록 구현하기 위해 우선순위큐를 사용할 경우 나무를 심을 때마다 매번 정렬을 수행하게 되므로 시간복잡도가 커지게 된다.

따라서 나무를 vector에 담은 다음 나무가 양분을 흡수하는 작업이 실행되기 전에 정렬이 이루어지도록 구현하는 것이 효율적이다.

---

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

class Land {
private:
	int landSize;
	int nutrients[11][11];
	vector<int> livingTree[11][11];
	queue<int> deadTree[11][11];
public:
	Land(int N) : landSize(N) {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				nutrients[y][x] = 5;
			}
		}
	}

	// 현재 심어진 나무의 개수를 반환한다.
	int getTreeCount() {
		int treeCnt = 0;
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				treeCnt += livingTree[y][x].size();
			}
		}

		return treeCnt;
	}

	// 나무를 심는다
	void plantTree(int y, int x, int treeAge) {
		if (y >= 1 && y <= landSize && x >= 1 && x <= landSize) {
			livingTree[y][x].push_back(treeAge);
		}
		else
			return;
	}

	// 나무가 땅의 양분을 흡수한다.
	void nourishTheTree() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				queue<int> growingTree;

				sort(livingTree[y][x].begin(), livingTree[y][x].end(), greater<int>());

				while (!livingTree[y][x].empty()) {
					int treeAge = livingTree[y][x].back();
					livingTree[y][x].pop_back();

					if (nutrients[y][x] >= treeAge) {
						nutrients[y][x] -= treeAge;
						growingTree.push(treeAge + 1);
					}
					else {
						deadTree[y][x].push(treeAge);
					}
				}

				while (!growingTree.empty()) {
					int treeAge = growingTree.front();
					growingTree.pop();

					livingTree[y][x].push_back(treeAge);
				}
			}
		}
	}

	// 땅의 양분을 증가시킨다.
	void increaseNutrients(int y, int x, int val) {
		if (y >= 1 && y <= landSize && x >= 1 && x <= landSize)
			nutrients[y][x] += val;
		else
			return;
	}

	// 죽은 나무가 땅의 양분으로 변환된다.
	void convertToNutrients() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				while (!deadTree[y][x].empty()) {
					int newNutrients = deadTree[y][x].front() / 2;
					deadTree[y][x].pop();

					increaseNutrients(y, x, newNutrients);
				}
			}
		}
	}

	// 나이가 5의 배수인 나무가 번식한다.
	void treeMultiply() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				int treeSize = livingTree[y][x].size();
				for (int i = 0; i < treeSize; i++) {
					int treeAge = livingTree[y][x][i];
					if (treeAge % 5 == 0) {
						for (int i = -1; i < 2; i++) {
							for (int j = -1; j < 2; j++) {
								if (i == 0 && j == 0) continue;
								plantTree(y + i, x + j, 1);
							}
						}
					}
				}
			}
		}
	}
};

class Robot {
private:
	int landSize;
	int nutrients[11][11];
public:
	Robot(int N) : landSize(N) { }

	// 공급하는 양분의 양을 설정한다.
	void setNutrients() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				cin >> nutrients[y][x];
			}
		}
	}

	// 땅에 양분을 공급한다.
	void supplyNutrients(Land& land) {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				land.increaseNutrients(y, x, nutrients[y][x]);
			}
		}
	}
};

void springAction(Land& land) {
	land.nourishTheTree();
}

void summerAction(Land& land) {
	land.convertToNutrients();
}

void fallAction(Land& land) {
	land.treeMultiply();
}

void winterAction(Land& land, Robot& robot) {
	robot.supplyNutrients(land);
}

void printYearsHavePassed(Land& land, Robot& robot, int K) {
	for (int i = 0; i < K; i++) {
		springAction(land);
		summerAction(land);
		fallAction(land);
		winterAction(land, robot);
	}

	cout << land.getTreeCount() << endl;
}

int main(void) {
	int N, M, K;
	cin >> N >> M >> K;

	Land land(N);
	Robot S2D2(N);

	S2D2.setNutrients();

	for (int i = 0; i < M; i++) {
		int x, y, z;
		cin >> y >> x >> z;
		land.plantTree(y, x, z);
	}

	printYearsHavePassed(land, S2D2, K);

	return 0;
}