(BOJ) 16235 나무 재테크

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

 

문제 풀이:

deque로 나무 위치랑 나이 저장 

봄

현재 존재 하는 나무 처음부터(나이 어린 나무부터) 보면서 (pop_front())

자기 나이만큼 양분 먹을 수 있으면 먹고 나이 증가 시켜서 다시 push_back()

못 먹으면 죽음 -> 죽는 나무 위치랑 나이 따로 큐에 저장 

 

여름

위에서 죽은 나무들 큐 빌 때까지 돌리면서 양분 추가

 

가을

나무 deque 돌리면서 번식 가능한 나무 찾아서 따로 큐에 위치 저장

다 돌렸으면 저장해둔 큐 빌 때까지 돌리면서 번식시킴 

새로운 나무는 항상 나이가 1로 가장 어리기 때문에 push_front()

 

겨울

양분 추가

 

소스코드:

typedef pair<int, int> P;
int n, m, k, bab[11][11],cur[11][11],Countdead;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
deque<pair<P, int> > tree;
queue<pair<P, int>> die;
queue<P > tmp;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	cin >> n >> m >> k ;
	for (int i = 0; i < n; i++) {
		for(int j=0;j<n;j++){
			cur[i][j] = 5;
			cin >> bab[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y, age;
		cin >> x >> y >> age;
		tree.push_back({ {x-1,y-1},age });
	}
	sort(tree.begin(), tree.end());

	for (int z = 0; z < k; z++) {
		//spring
		int len = tree.size();
		for (int i = 0; i < len;i++) {
			int x = tree.front().first.first;
			int y = tree.front().first.second;
			int age = tree.front().second;
			tree.pop_front();
			if (cur[x][y] >= age) {
				cur[x][y] -= age;
				tree.push_back({ {x,y},age + 1 });
			}
			else {
				die.push({ {x,y},age });
			}
		}
	
		//summer
		while (!die.empty()) {
			int x = die.front().first.first;
			int y = die.front().first.second;
			int age = die.front().second;
			die.pop();
			cur[x][y] += age / 2;
		}
		// fall
		len = tree.size();
		for (int i = 0; i < len; i++) {
			int x = tree.front().first.first;
			int y = tree.front().first.second;
			int age = tree.front().second;
			tree.pop_front();
			if (age % 5 == 0) tmp.push({ x,y });
			
			tree.push_back({ {x,y},age });
		}
		while (!tmp.empty()) {
			int x = tmp.front().first;
			int y = tmp.front().second;
			tmp.pop();
			for (int j = 0; j < 8; j++) {
				if (x + dx[j] < 0 || x + dx[j] >= n || y + dy[j] < 0 || y + dy[j] >= n) continue;
				tree.push_front({ {x + dx[j],y + dy[j]},1 });
			}
		}
		//winter
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cur[i][j] += bab[i][j];
			}
		}
	}
	cout << tree.size() << '\n';
	return 0;
}