백준 16235번 - 나무 재테크

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

16235번: 나무 재테크

[풀이]

​

깡(?) 시뮬레이션 문제이다.

​

K년 만큼 for문을 돌리면서 1년마다 봄, 여름, 가을, 겨울에 수행해야 할 일들을 순차적으로 실행한 뒤에 남아있는 나무의 수를 구하면 된다.

​

여기서 가장 중요한 점은 나무를 우선순위 큐로 관리하는 것이다.

​

<봄> 시기에 나이가 어린 나무부터 양분을 먹거나 죽어야 하기 때문에 우선순위 큐에 나이 기준 오름차순으로 나무를 넣어준다.

​

땅의 각 칸에 나무가 있다고 설명되어 있어서 이차원 배열 각 칸에 나무들의 정보를 넣으려고 할 수 있지만,

​

결국 나무들은 자신의 칸에 관련된 일을 수행하기 때문에 우선순위 큐에 나무를 넣을 때 (Y좌표, X좌표, 나이) 정보를 갖는 일차원 배열을 넣어주면 된다.

​

그 후 우선순위 큐에서 나무를 한 개씩 remove하면서 일을 수행하면 된다.

​

추가적으로 <여름>과 <가을> 일을 수행하기 편하게 큐를 두 개 더 선언했다.

- deadTree : 봄에 양분을 먹지 못해 죽은 나무들을 넣는 큐 ( <여름> 일을 수행하기 위해서 )

- tq : 봄에 양분을 먹고 나이가 1 증가한 나무들을 넣는 큐 ( <가을> 일을 수행하기 위해서 )

​

<여름> 과 <가을> 에는 각각 deadTree와 tq에 들어있는 나무들을 remove하면서 큐가 빌 때 까지 각각 일을 수행한다.

​

<가을> 에서 나이가 1인 나무가 생기면 처음에 생성한 우선순위 큐에 넣어주고, <가을> 일을 수행한 나무도 우선순위 큐에 넣어준다.

​

이렇게하면 우선순위 큐에는 다음 년도에 다시 일을 수행할 나무들이 나이 순으로 들어가게 된다.

​

<겨울>은 그냥 이중 for문 한 번 돌리면 된다.

​

​

[소스코드]

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class bj16235 {	// bj 16235 나무재테크
	static int[] dx= {0,1,1,1,0,-1,-1,-1};
	static int[] dy= {-1,-1,0,1,1,1,0,-1};
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		int k=sc.nextInt();
		int[][] nong=new int[n+1][n+1];
		int[][] yang=new int[n+1][n+1];
		PriorityQueue<int[]> q=new PriorityQueue<int[]>(new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				return o1[2]-o2[2];
			}
		});
		Queue<int[]> deadTree=new LinkedList<int[]>();
		Queue<int[]> tq=new LinkedList<int[]>();
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				yang[i][j]=sc.nextInt();
				nong[i][j]=5;
			}
		}
		for(int i=0;i<m;i++) {
			int namuY=sc.nextInt();
			int namuX=sc.nextInt();
			int namuAge=sc.nextInt();
			int[] node= {namuY,namuX,namuAge};
			q.add(node);
		}
		for(int year=1;year<=k;year++) {
			// 봄
			while(!q.isEmpty()) {
				int[] temp=q.remove();
				int y=temp[0];
				int x=temp[1];
				int age=temp[2];
				if(nong[y][x]<age) {
					deadTree.add(temp);
				}
				else {
					nong[y][x]-=age;
					int[] next= {y,x,age+1};
					tq.add(next);
				}
			}
			//여름
			while(!deadTree.isEmpty()) {
				int[] dead=deadTree.remove();
				int deadY=dead[0];
				int deadX=dead[1];
				int deadAge=dead[2]>>1;
				nong[deadY][deadX]+=deadAge;
			}
			//가을
			while(!tq.isEmpty()) {
				int[] burn=tq.remove();
				int burnY=burn[0];
				int burnX=burn[1];
				int burnAge=burn[2];
				if(burnAge%5==0) {
					for(int d=0;d<8;d++) {
						int ty=burnY+dy[d];
						int tx=burnX+dx[d];
						if(ty<=0||ty>n||tx<=0||tx>n) continue;
						int[] next= {ty,tx,1};
						q.add(next);
					}
				}
				q.add(burn);
			}
			// 겨울
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					nong[i][j]+=yang[i][j];
				}
			}
		}
		int count=0;
		while(!q.isEmpty()) {
			int[] live=q.remove();
			count++;
		}
		System.out.println(count);
	}
}