[BOJ] 16235 나무 재테크

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static class Tree {
		int r,c,age;
		Tree(int r,int c,int age){
			this.r = r;
			this.c = c;
			this.age = age;
		}
	}
	static int[] dr = {-1,-1,0,1,1,1,0,-1};
	static int[] dc = {0,1,1,1,0,-1,-1,-1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[][] map = new int[n+1][n+1];
		int[][] add = 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++) {
				map[i][j] = 5;
				add[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		Queue<Tree> trees = new LinkedList<>();
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			trees.add(new Tree(r,c,z));
		}
		while(k-->0) {
			List<Tree> list = new ArrayList<>(trees);
			Collections.sort(list,(a,b)->{
				return a.age - b.age;
			});
			trees = new LinkedList<>();
			Queue<Tree> remove = new LinkedList<>();
			int size = list.size();
			for(int i=0;i<size;i++) {
				Tree tree = list.get(i);
				if(map[tree.r][tree.c]>=tree.age) {
					map[tree.r][tree.c] -= tree.age;
					trees.offer(new Tree(tree.r,tree.c,tree.age+1));
				}
				else {
					remove.offer(tree);
				}
			}
			for(Tree tree : remove) {
				map[tree.r][tree.c] += tree.age / 2;
			}
			size = trees.size();
			for(int i=0;i<size;i++) {
				Tree tree = trees.poll();
				if(tree.age%5 == 0) {
					for(int d=0;d<8;d++) {
						int nr = tree.r + dr[d];
						int nc = tree.c + dc[d];
						if(nr<=0 || nr>n || nc<=0 || nc>n) continue;
						trees.add(new Tree(nr,nc,1));
					}
				}
				trees.offer(tree);
			}
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					map[i][j] += add[i][j];
				}
			}
		}
		System.out.println(trees.size());
	}
}