[삼성기출]백준16235 - 나무 재테크

package sw;

import java.io.*;
import java.util.*;

public class Main {
	static int N,M,K;
	static Area[][] areas;
	static int[][] nourish;
	
	//8방향
	static int[][] dir = //우상,우,우하,하,좌하,좌,좌상,상 8방향
	static boolean check(int x, int y) {
		if(x>=0 && x<nourish.length && y>=0 && y<nourish[x].length)
			return true;
		else return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().trim().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		K = Integer.parseInt(input[2]);
		
		/*
		 * 각 구역 초기화
		 */
		areas = new Area[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				areas[i][j] = new Area();
			}
		}
		/*
		 * 추가 양분 맵.
		 */
		nourish = new int[N][N];
		String[] str= null;
		for(int i=0; i<N; i++) {
			str = br.readLine().trim().split(" ");
			for(int j=0; j<N; j++){
				nourish[i][j] = Integer.parseInt(str[j]);
			}
		}
		
		/*
		 * 입력되는 초기 나무들 셋팅.
		 */
		for(int i=0; i<M; i++) {
			str = br.readLine().trim().split(" ");
			areas[Integer.parseInt(str[0])-1][Integer.parseInt(str[1])-1].trees.add(Integer.parseInt(str[2]));
		}
		
		/*
		 * K년 동안 작업.
		 */
		for(int y=1; y<=K; y++) {
			springAndSummer();
			fallAndWinter();
		}
		
		System.out.println(result());
	}
	/*
	 * 연관성있는 계절끼리 묶어서 수를 만들었음.
	 * 봄과 여름
	 */
	static void springAndSummer() {
		int n,age;
		Queue<Integer> tmp = null;
		Queue<Integer> qu = null;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(areas[i][j].trees.size()==0) continue;
				n = areas[i][j].n;
				tmp = new PriorityQueue<>();
				qu = areas[i][j].trees;
				while(!qu.isEmpty()) {
					age = qu.peek();
					if(n >= age) {
						qu.poll();
						n-=age;
						tmp.add(age+1);
						if((age+1)%5 == 0)
							areas[i][j].five++;
					}else break;
				}
				while(!qu.isEmpty()) {
					n += qu.poll()/2;
				}
				areas[i][j].n = n;
				areas[i][j].trees = tmp;
			}
		}
	}
	
	/*
	 * 가을과 겨울
	 */
	static void fallAndWinter() {
		int dx,dy;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(areas[i][j].five > 0) {
					for(int d=0; d<8; d++) {
						dx = i + dir[d][0];
						dy = j + dir[d][1];
						if(check(dx,dy))
							for(int m=0; m<areas[i][j].five; m++) {
								areas[dx][dy].trees.add(1);
							}
					}
					areas[i][j].five = 0;
				}
				areas[i][j].n += nourish[i][j];
			}
		}
	}
	
	/*
	 * 각 구역마다 나무 갯수 결과
	 */
	static int result() {
		int res = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				res += areas[i][j].trees.size();
			}
		}
		return res;
	}
	
	static void print() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				System.out.print(areas[i][j].n+" ");
			}
			System.out.println();
		}
		System.out.println("=====================");
	}
	
	/*
	 * n: 영양분.
	 * five: 나이가 5개인 나무 갯수.
	 * tress: 나이를 담고있는 나무들.
	 */
	static class Area {
		int n;
		int five;
		Queue<Integer> trees;
		// 우선순위큐로 나이가 작은것부터 오름차순으로 정렬.
		
		public Area() {
			this.n = 5;
			this.trees = new PriorityQueue<>(); 
			five = 0;
		}
		
	}
}