[백준] 16235 나무 재테크 - 시뮬레이션 + 우선순위큐(Priority Queue) + 자료구조 + 시간초과 JAVA

 

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

16235번: 나무 재테크

코드설명

시뮬레이션, 우선순위큐를 활용한 시간초과 해결 문제입니다.

 

문제조건을 보면 시간제한이 0.3 초 입니다.

처음에 문제를 보고 PriorityQueue[][] graph 를 선언하여 각 자리마다의 나이를 연결시키는 방안으로 진행하려했지만,

이렇게 할경우 결국 항상 N*N의 맵을 확인하면서 나무를 확인해야합니다. N이 <=10 보다 작은 조건이 있어서 애매하지만, 가능했을 것 같습니다.

 

하지만, 그 방법보다 우선순위큐를 GLobal하게 선언하여 한곳에서 관리합니다.

이떄, 제가 실수했던 부분은

1. 우선순위큐에 qSize를 두고서 한턴씩만 진행하려했지만, 우선순위큐는 값이 새로 들어오면 해당 값에 맞추어서 큐의 순서가 재정렬된다는점을 간과했습니다. 그렇기에 새로운 pqTemp를 두고서 저장시키며 진행했습니다.

이때, pqTemp를 깊은복사를 통해서 pq에 새로 직접 다 넣어도되고, pqTemp로 얕은복사를 시킨뒤, 다시 사용할떄 pqTemp에 다시 PriorityQueue를 재선언하여 사용하는것이 좀 더 속도가 빠를 것 입니다.

2. Node의 생성자에 this.r = r , this.c=c를 뺴먹어서 오류를 찾는데 시간이 조금 걸렸습니다..

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	//PriorityQueue 사용시 이렇게 qSize로 하면안됩니다. 나이값에 따라서 값이 정렬되기에 그렇습니다.
	public static int N, M, K;
	public static int answer;
	public static int[][] arr;
	public static int[][] energy;
	public static PriorityQueue<Node> pq = new PriorityQueue<>();
	public static PriorityQueue<Node> pqTemp = new PriorityQueue<>();
	public static PriorityQueue<Node> pqTemp2 = new PriorityQueue<>();
	public static Queue<Node> deadTreeQ = new LinkedList<>();
	public static StringBuilder sb = new StringBuilder();
	public static int[] dx = {-1,-1,-1,0,1,1,1,0}; //11시 방향에서부터 시계방향으로 돕니다.
	public static int[] dy = {-1,0,1,1,1,0,-1,-1};
	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());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N][N];
    	energy = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    			energy[i][j] = 5; //초기값의 음식은 5입니다.
    		}
    	}
    	
    	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 z = Integer.parseInt(st.nextToken()); //나무의 나이
    		pq.offer(new Node(x-1, y-1, z));
    	}
    	
    	simulate();
    	System.out.println(pq.size());
	}
	
	public static void simulate() {
		
		while(K-- > 0) {
			
			//봄 처리. 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가한다. 나무는 나무가 있는 1x1 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
			//만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
			pqTemp = new PriorityQueue<Node>();
			int pqSize = pq.size();
			for(int i=0;i<pqSize;i++) {
				Node temp = pq.poll();
				if(energy[temp.r][temp.c] >= temp.age ) { //나무가 양분을 먹습니다.
					energy[temp.r][temp.c] -= temp.age;
//					pq.offer(new Node(temp.r, temp.c, temp.age + 1));
					pqTemp.offer(new Node(temp.r, temp.c, temp.age + 1));
				}else { //만약 양분을 먹지못한다면 바로 죽는다.
					deadTreeQ.add(temp); 	
				}
			}
			pq = pqTemp;
//			while(!pqTemp.isEmpty()) {
//				pq.offer(pqTemp.poll());
//			}
			
			
			//여름 : 봄에 죽은 나무가 양분으로 변하게 됩니다. 각각의 죽은 나무마다 나이를 2로 나눈값이 나무가 있던 칸에 양분으로 추가됩니다. 소수점 아래는 버립니다.
			while(!deadTreeQ.isEmpty()) {
				Node temp = deadTreeQ.poll();
				energy[temp.r][temp.c] += temp.age / 2;
			}
			
			//가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생깁니다.
			//어떤 칸 (r, )와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.
			pqSize = pq.size();
			pqTemp = new PriorityQueue<Node>();
//			pqTemp2 = new PriorityQueue<Node>();
			for(int i=0;i<pqSize;i++) {
				Node temp = pq.poll();
				if(temp.age % 5 == 0) {
					for(int dir = 0;dir<8;dir++) {
						int nr = temp.r + dx[dir];
						int nc = temp.c + dy[dir];
						if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
//						pq.offer(new Node(nr, nc, 1));
						pqTemp.offer(new Node(nr, nc, 1));
					}				
				}
				pqTemp.offer(temp);
			}
			pq = pqTemp;
//			while(!pqTemp2.isEmpty()) {
//				pq.offer(pqTemp2.poll());
//			}
			
			
			//겨울 : S2D3가 땅을 돌아다니면서 땅에 양분을 추가합니다. 각 칸에 추가되는 야분의 양은 A[r][c]이고, 입력으로 주어집니다.
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					energy[i][j] += arr[i][j];
				}
			}
			
		}
		
	}
	
}

class Node implements Comparable<Node>{
	int r;
	int c;
	int age;
	public Node(int r, int c, int age) {
		this.r=r;
		this.c=c;
		this.age = age;
	}
	@Override
	public int compareTo(Node other) { //나이가 적은순이 우선순위가 되도록 합니다.
		return this.age - other.age;
	}
}