[C++] 백준 16235번 나무 재테크

16235번: 나무 재테크

삼성 SW 역량 테스트 기출 문제 소속 문제.

구현 / 시뮬레이션 문제 중 골드4지만 꽤 낮은 정답률인 문제이다.

아마 나 포함 대부분 시간 초과 문제가 발생하는 것 같다.

 

문제 조건

문제의 힌트는 다음과 같다.

• 땅의 크기가 N x N이다.
• (r, c)은 r은 행, c는 열을 의미.
• S2D2라는 로봇은 양분을 추가해줌.
• 맨 처음 5만큼의 양분이 각 칸에 존재

 

또한 다음과 같은 순서로 진행된다.

처음에 주어진 조건

1. M개의 나무를 구매한다.
2. 여러 개 나무가 같은 칸이 가능하다.
3. 사계절에 따라 추가 조건이 진행됨.

사계절은 다음과 같은 조건이다.

봄

1. 나무가 자신의 나이만큼 양분을 먹는데,
   여러 개의 나무가 있을 시 어린 나무부터 양분을 먹고
   자기 나이만큼 양분을 먹지 못하면 바로 죽는다.
2. 양분을 먹은 나무는 나이가 1 증가한다.
3. 1x1 칸, 즉 나무가 있는 칸만큼의 양분만 먹는다.

여름

1. 죽은 나무가 양분이 된다. 나무의 나이/2가 해당 땅에 양분으로 추가된다.

가을

1. 나이가 5의 배수인 나무가 번식을 한다.
2. 인접한 8개의 칸에 나이가 1인 나무가 생기는데, 존재하지 않는 칸에는 생성되지 않는다.

겨울

1. S2D2 로봇이 돌아다니며 양분을 추가해준다.

처음 이 문제를 보았을 때,

사실 이 문제를 시도한 건 꽤 됐었다.

실제로 푼 건 오늘인데, 이전에 틀렸던 방식으로 계속 시도했었다.

우선순위 큐를 이용해서 나무의 정보를 모두 담아두었다가 어린 나무부터 양분을 먹는 방식으로 시도했다.

 

이 문제는 시간 제한이 0.3초로 상당히 짧다.

따라서 계속해서 정렬을 시도하는 우선순위 큐로는 해당 문제를 풀 수 없다.

 

문제 풀이

나의 경우에는 결국 해결하지 못하고 질문 게시판을 찾아서 풀었다.

우선 최대 나이까지 큐를 생성해서 모든 나이를 조사한 후에 나무가 존재하는 큐에서 pop()한 후에

해당 나무가 양분을 먹을 수 있는지를 조사해서 먹을 수 있다면 다음 나이의 큐에 push해주고,

먹을 수 없다면 죽은 나무로, 땅에 양분으로 추가해준다.

 

이 때, 다음 나이의 큐에 바로 push하면 다음 나이를 조사할 때 해당 나무를 다시 조사하므로,

벡터를 하나 생성해주어서 해당 벡터에 담아두었다가 나이 조사가 모두 끝난 후에 한꺼번에 push해준다.

마찬가지로 죽은 나무도 위와 같은 방식으로 해결해준다.

/*
* 백준 16235번 나무 재테크
* https://www.acmicpc.net/problem/16235
* 문제 유형
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Tree {
public:
	int r;
	int c;
	int age;
	Tree(int r, int c, int age) {
		this->r = r;
		this->c = c;
		this->age = age;
	}
};

int	widthHeight, firstTreeCnt, maxYear;
int currentFeed[11][11];
int feed[11][11];
int result;
queue<Tree> currentTreeQ[1012];
vector<Tree> deadTreeVec;
pair<int, int> direction[8] = {
	{-1, 0},
	{-1, 1},
	{0, 1},
	{1, 1},
	{1, 0},
	{1, -1},
	{0, -1},
	{-1, -1}
};

void spring() {
	vector<Tree> treeVec;
	for (int i = 1; i <= 1011; i++) {
		while (!currentTreeQ[i].empty()) {

			Tree tree = currentTreeQ[i].front();
			currentTreeQ[i].pop();
			int r = tree.r;
			int c = tree.c;

			if (currentFeed[r][c] < tree.age) {
				deadTreeVec.push_back(tree);
				continue;
			}
			else {
				currentFeed[r][c] -= tree.age;
				tree.age++;
				treeVec.push_back(tree);
			}
		}
	}

	for (Tree tree : treeVec) {
		currentTreeQ[tree.age].push(tree);
	}

}

void summer() {
	for (Tree tree : deadTreeVec) {
		int r = tree.r;
		int c = tree.c;
		int feed = tree.age / 2;

		currentFeed[r][c] += feed;
	}
	deadTreeVec.clear();
}

void fall() {
	for (int i = 1; i <= 1011; i++) {
		int size = currentTreeQ[i].size();
		while (size--) {
			Tree tree = currentTreeQ[i].front();
			currentTreeQ[i].pop();
			currentTreeQ[i].push(tree);
			if (tree.age % 5 != 0) {
				continue;
			}

			for (pair<int, int> dir : direction) {
				int newR = tree.r + dir.first;
				int newC = tree.c + dir.second;

				if (newR < 1 || newR > widthHeight || newC < 1 || newC > widthHeight) {
					continue;
				}

				currentTreeQ[1].push(Tree(newR, newC, 1));
			}
		}
	}
}

void winter() {
	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			currentFeed[i][j] += feed[i][j];
		}
	}
}

void fourSeason(int year) {
	if (year > maxYear) { return; }

	spring();
	summer();
	fall();
	winter();

	fourSeason(year + 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> widthHeight >> firstTreeCnt >> maxYear;

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			cin >> feed[i][j];
			currentFeed[i][j] = 5;
		}
	}

	int x, y, age;

	for (int i = 1; i <= firstTreeCnt; i++) {
		cin >> x >> y >> age;
		currentTreeQ[age].push(Tree(x, y, age));
	}

	fourSeason(1);

	for (int i = 1; i <= 1011; i++) {
		result += currentTreeQ[i].size();
	}

	cout << result;

	return 0;
}

최종적으로 나무가 존재하는 큐에서 size를 구해서 출력해준다.

 

백준 16235번 나무 재테크 · kimyunseok/cpp@8209837