16235. 나무재테크

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

16235번: 나무 재테크

<JAVA>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

	static final int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static final int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

	public static void main(String[] args) throws Exception {
		class TREE implements Comparable<TREE> {
			TREE(int x, int y, int age) {
				this.x = x;
				this.y = y;
				this.age = age;
			}

			int x, y, age;

			@Override
			public int compareTo(TREE o) { // 나이가 적은 나무부터 나오게 하기 위해 연산자 재 지정
				return Integer.compare(this.age, o.age);
			}
		}

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n, m, k;
		Queue<TREE> tree[] = new LinkedList[2];
		tree[0] = new LinkedList<>();
		tree[1] = new LinkedList<>();
		List<TREE> init_tree = new ArrayList<>();
		Queue<TREE> new_tree = new LinkedList<>();
		Queue<TREE> dead_tee = new LinkedList<>();
		Queue<TREE> birth_possible_tree = new LinkedList<>();
		int map[][] = new int[10][10];
		int income[][] = new int[10][10];

		st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken(" "));
		m = Integer.parseInt(st.nextToken(" "));
		k = Integer.parseInt(st.nextToken(" "));
		for (int i = 0; i < n; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; ++j) {
				income[j][i] = Integer.parseInt(st.nextToken(" "));
				map[j][i] = 5;
			}
		}
		for (int i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			init_tree.add(new TREE(Integer.parseInt(st.nextToken(" ")) - 1, Integer.parseInt(st.nextToken(" ")) - 1,
					Integer.parseInt(st.nextToken(" ")))); // 0,0 부터 시작을 위해 1을 빼준다
		}
		Collections.sort(init_tree);
		int cur = 0, next = 0;
		for (int i = 0; i < m; ++i) {
			tree[cur].add(init_tree.get(i));
		}
		for (int i = 0; i < k; ++i) {
			next = (cur + 1) % 2;

			// 봄은 나이 순으로 진행하므로, 새로운 나무부터 양분을 준다.
			while (!new_tree.isEmpty()) { // 새로운 나무
				TREE cur_tree = new_tree.poll();
				if (map[cur_tree.y][cur_tree.x] >= cur_tree.age) { // 양분이 충분하면
					map[cur_tree.y][cur_tree.x] -= cur_tree.age; // 양분을 준다.
					++cur_tree.age; // 나이 증가
					tree[next].add(cur_tree); // 내년에 사용할 큐에 넣어준다.
				} else {
					dead_tee.add(cur_tree); // 양분이 없으면 죽는다.
				}
			}
			while (!tree[cur].isEmpty()) { // 현재 나무
				TREE cur_tree = tree[cur].poll();
				if (map[cur_tree.y][cur_tree.x] >= cur_tree.age) { // 양분이 충분하면
					map[cur_tree.y][cur_tree.x] -= cur_tree.age; // 양분을 준다.
					++cur_tree.age; // 나이 증가
					tree[next].add(cur_tree); // 내년에 사용할 큐에 넣어준다.
					if ((cur_tree.age % 5) == 0) { // 나이가 5의 배수라면
						birth_possible_tree.add(cur_tree); // 주변에 나무를 심을 준비한다.
					}
				} else {
					dead_tee.add(cur_tree); // 양분이 없으면 죽는다.
				}
			}
			while (!dead_tee.isEmpty()) { // 죽은 나무가 있으면 (여름)
				TREE cur_tree = dead_tee.poll();
				map[cur_tree.y][cur_tree.x] += (cur_tree.age / 2); // 땅에 양분을 추가해준다.
			}

			while (!birth_possible_tree.isEmpty()) { // 나무 번식 (가을)
				TREE cur_tree = birth_possible_tree.poll();
				for (int dir = 0; dir < 8; ++dir) {
					TREE next_tree = new TREE(cur_tree.x + dx[dir], cur_tree.y + dy[dir], 1);
					if (next_tree.y < 0 || next_tree.y >= n || next_tree.x < 0 || next_tree.x >= n) {
						continue;
					}
					new_tree.add(next_tree);
				}
			}
			for (int y = 0; y < n; ++y) { // 땅에 양분 공급(겨울)
				for (int x = 0; x < n; ++x) {
					map[y][x] += income[y][x];
				}
			}
			cur = next; // 1년 증가
		}
		System.out.println(tree[next].size() + new_tree.size());
	}

}

<C++>

#include <iostream>
#include <algorithm>
#include<queue>
using namespace std;
struct TREE {
	int x, y, age;
	bool operator < (TREE& a)			//나이가 적은 나무부터 나오게 하기 위해 연산자 재 지정
	{
		return (age < a.age);
	}
};
int n, m, k;
queue<TREE> tree[2];
queue<TREE> new_tree;					// 새로운 나무
queue<TREE> dead_tee;					// 죽은 나무
queue<TREE> birth_possible_tree;		// 번식 가능 나무
TREE init_tree[100];					// 문제 조건에서 나무는 최대 100이라고 정함.
int map[10][10];
int income[10][10];
const int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
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) {
			cin >> income[i][j];
			map[i][j] = 5;
		}
	}
	for (int i = 0; i < m; ++i) {
		cin >> init_tree[i].x >> init_tree[i].y >> init_tree[i].age;
		--init_tree[i].x, --init_tree[i].y;		// 0,0 부터 시작을 위해 빼 준다.
	}
	sort(init_tree, init_tree + m);				// 정렬
	int cur = 0, next = 0;
	for (int i = 0; i < m; ++i) {
		tree[cur].push(init_tree[i]);
	}
	for (int i = 0; i < k; ++i) {
		next = (cur + 1) % 2;
		// 봄은 나이 순으로 진행하므로, 새로운 나무부터 양분을 준다.
		while (!new_tree.empty()) {								// 새로운 나무
			TREE cur_tree = new_tree.front(); new_tree.pop();

			if (map[cur_tree.x][cur_tree.y] >= cur_tree.age) {	// 양분이 충분하면
				map[cur_tree.x][cur_tree.y] -= cur_tree.age;	// 양분을 준다.
				++cur_tree.age;									// 나이 증가
				tree[next].push(cur_tree);						// 내년에 사용할 큐에 넣어준다.
			}
			else {
				dead_tee.push(cur_tree);						// 양분이 없으면 죽는다.
			}
		}
		while (!tree[cur].empty()) {							// 현재 나무
			TREE cur_tree = tree[cur].front(); tree[cur].pop();
			if (map[cur_tree.x][cur_tree.y] >= cur_tree.age) {	// 양분이 충분하면
				map[cur_tree.x][cur_tree.y] -= cur_tree.age;	// 양분을 준다.
				++cur_tree.age;									// 나이 증가
				tree[next].push(cur_tree);						// 내년에 사용할 큐에 넣어준다.
				if ((cur_tree.age % 5) == 0) {					// 나이가 5의 배수라면
					birth_possible_tree.push(cur_tree);			// 주변에 나무를 심을 준비한다.
				}
			}
			else {
				dead_tee.push(cur_tree);						// 양분이 없으면 죽는다.
			}
		}
		while (!dead_tee.empty()) {								// 죽은 나무가 있으면 (여름)
			TREE cur_tree = dead_tee.front();   dead_tee.pop();
			map[cur_tree.x][cur_tree.y] += (cur_tree.age / 2);	// 땅에 양분을 추가해준다.
		}

		while (!birth_possible_tree.empty()) {					// 나무 번식 (가을)
			TREE cur_tree = birth_possible_tree.front();    birth_possible_tree.pop();
			for (int dir = 0; dir < 8; ++dir) {
				TREE next_tree;
				next_tree.x = cur_tree.x + dy[dir];
				next_tree.y = cur_tree.y + dx[dir];
				next_tree.age = 1;
				if (next_tree.x < 0 || next_tree.x >= n || next_tree.y < 0 || next_tree.y >= n) {
					continue;
				}
				new_tree.push(next_tree);
			}
		}
		for (int x = 0; x < n; ++x) {							// 땅에 양분 공급(겨울)
			for (int y = 0; y < n; ++y) {
				map[x][y] += income[x][y];
			}
		}
		cur = next;												// 1년 증가
	}
	cout << tree[next].size() + new_tree.size();
	return 0;
}