백준 : 16235

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

16235번: 나무 재테크

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class B16235 {
	static class Tree implements Comparable<Tree> {
		int age;
		boolean live;

		Tree(int age) {
			this.age = age;
			this.live = false;
		}

		Tree(int age, boolean live) {
			this.age = age;
			this.live = live;
		}

		@Override
		public int compareTo(Tree o) {
			// TODO Auto-generated method stub
			if (this.age > o.age) {
				return 1;
			} else {
				return -1;
			}
		}
	}

	static int N, M, K;
	static int[][] A;
	static int[][] map;
	static ArrayList<Tree>[][] tree;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		tree = new ArrayList[N + 1][N + 1];
		A = new int[N + 1][N + 1];
		map = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
				map[i][j] = 5;
				tree[i][j] = new ArrayList<Tree>();
			}
		}

		int y, x, z;
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			y = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());
			z = Integer.parseInt(st.nextToken());

			tree[y][x].add(new Tree(z));
		}
		int[] dy = { 0, 0, 1, -1, 1, -1, 1, -1 };
		int[] dx = { 1, -1, 0, 0, 1, -1, -1, 1 };
		for (int k = 1; k <= K; k++) {
//			System.out.println("K = " + k);
			// 봄
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (tree[i][j].isEmpty())
						continue;
					// 나이순으로 정렬
					Collections.sort(tree[i][j]);

					// 양분먹기
					int seq = 0;
					for (seq = 0; seq < tree[i][j].size(); seq++) {
						if (map[i][j] >= tree[i][j].get(seq).age) {
							map[i][j] -= tree[i][j].get(seq).age;
							tree[i][j].set(seq, new Tree(tree[i][j].get(seq).age + 1, false));
						} else {
							tree[i][j].set(seq, new Tree(tree[i][j].get(seq).age, true));
						}
					}
//					System.out.println("tree " + i + " " + j + "나무");
//					for (int z1 = 0; z1 < tree[i][j].size(); z1++) {
//						System.out.print(tree[i][j].get(z1).age + " ");
//					}
//					System.out.println();

				}
			}
			// 여름
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (tree[i][j].isEmpty())
						continue;
					int seq = tree[i][j].size() - 1;
					for (; seq >= 0; seq--) {
						if (!tree[i][j].get(seq).live)
							break;
						map[i][j] += tree[i][j].get(seq).age / 2;
						tree[i][j].remove(seq);
					}
				}
			}
			// 가을
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (tree[i][j].isEmpty())
						continue;
					int seq = tree[i][j].size() - 1;
//					System.out.println("살아잇는 나무" + i + " " + j);
					for (; seq >= 0; seq--) {
						if (tree[i][j].get(seq).age % 5 == 0) {
							// 번식
							for (int d = 0; d < 8; d++) {
								int ny = dy[d] + i;
								int nx = dx[d] + j;
								if (ny < 1 || ny > N || nx < 1 || nx > N) {
									continue;
								}
//								System.out.println("번식 : " + ny + " " + nx);
								tree[ny][nx].add(new Tree(1));

							}
						}
					}
				}
			}
			// 겨울
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					map[i][j] += A[i][j];
				}
			}
		}
		// 살아있는 나무 개수
		int treeCnt = 0;
//		System.out.println("값 구하기");
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (tree[i][j].isEmpty())
					continue;
//				System.out.println(i +" "+j +"위치 나무살아잇음");
				treeCnt += tree[i][j].size();
			}
		}
		System.out.println(treeCnt);
	}
}