[BOJ] 백준 16235 나무 재테크

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int[] dr = {-1,-1,-1,0,1,1,1,0};
	static int[] dc = {-1,0,1,1,1,0,-1,-1};
	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 n,k;
	static int[][] add;
	static int[][] soil;
	static int result = 0;
	static Queue<Tree> q;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		add = new int[n+1][n+1];
		soil = 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++) {
				add[i][j] = Integer.parseInt(st.nextToken());
				soil[i][j] = 5;
			}
		}
		q = new LinkedList<>();
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int age = Integer.parseInt(st.nextToken());
			q.offer(new Tree(x,y,age));
		}
		while(k-->0) {
			season();
		}
		result = q.size();
		System.out.println(result);
	}
	private static void season() {
		List<Tree> list = new ArrayList<>(q);
		list.sort((a,b)-> a.age - b.age);
		q = new LinkedList<>();
		Queue<Tree> dead = new LinkedList<>();
		for(Tree t : list) {
			if(soil[t.r][t.c] >= t.age) {
				soil[t.r][t.c] -= t.age;
				q.offer(new Tree(t.r,t.c,t.age+1));
			}
			else {
				dead.offer(t);
			}
		}
		while(!dead.isEmpty()) {
			Tree t = dead.poll();
			soil[t.r][t.c] += (t.age / 2);
		}
		int size = q.size();
		for(int i=0;i<size;i++) {
			Tree t = q.poll();
			if(t.age % 5 == 0) {
				for(int d=0;d<8;d++) {
					int nr = t.r + dr[d];
					int nc = t.c + dc[d];
					if(nr<1 || nr>n || nc<1 || nc>n) continue;
					q.offer(new Tree(nr,nc,1));
				}
			}
			q.offer(t);
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				soil[i][j] += add[i][j];
			}
		}
	}
}