[Java/자바 백준 16235] 나무 재테크

풀이

 

문제 이해가 가장 중요한거 같습니다. 말이 좀 헷갈리게 해서

첫째줄은 N,M,K  이고 N은 맵의 크기, M은 나무 갯수, K는 몇년동안 진행하는지입니다.

그후 N개만큼 겨울에 양분이 추가되는 숫자가 나오구,

그다음 M개만큼 Tree에 x,y,age에 대한 정보가 나옵니다.

기본 map에는 전부 양분이 5인 디폴트 값이 있습니다.

 

나이가 낮은 나무들이 먼저 나올 수 있게 pq를 이용했습니다.

 

봄 )

양분이 충분할 때와 충분하지 않은 경우로 나누어서

충분하다면 map[x][y]에 age만큼 감소하고, age를 +1씩 해주었습니다.

이때 tmp 큐에 넣어주었는데, 왜냐하면 tree가 pq로 만들어줬기 때문에 tree에 넣어준다면 나이가 어린 나무가 하나 들어가서 정렬이 바뀔 수도 있기 때문입니다.

충분하지 않다면 tree_dead큐에 넣어줬습니다. 

처음 tree_dead도 pq로 만들어줬지만, 그럴 필요도 없고 시간초과도 나드라구요.

 

여름)

죽은 나무 큐들을 /2 해주고 map에 양분을 더해줬습니다.

 

가을)

나무가 5의 배수라면 8방 탐색을 진행했습니다.

 

겨울)

plus[x][y]를 map[x][y]에 더해줬습니다.

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

class Tree implements Comparable<Tree>{
	int x,y,age;

	public Tree(int x, int y, int age) {
		super();
		this.x = x;
		this.y = y;
		this.age = age;
	}

	@Override
	public int compareTo(Tree o) {
		// TODO Auto-generated method stub
		return Integer.compare(this.age, o.age);
	}
	
}

public class Main {
	static int N,M,K;
	static int[][] plus,map;
	static int[] dx = {0,-1,-1,-1,0,1,1,1};
	static int[] dy = {-1,-1,0, 1,1,1,0,-1};
	static PriorityQueue<Tree> tree = new PriorityQueue<>();
	static Queue<Tree> tree_dead = new LinkedList<>();
	static Queue<Tree> tmp = new LinkedList<Tree>();
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		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());
		
		plus = new int[N][N];
		map = new int[N][N];
		for(int i = 0 ; i<N ; i ++) {
			st = new StringTokenizer(br.readLine()," ");
			for(int j = 0 ; j<N ; j++ ) {
				plus[i][j] = Integer.parseInt(st.nextToken());
				map[i][j] = 5;
			}
		}
		for(int i =  0 ; i<M ; i++) {
			st = new StringTokenizer(br.readLine()," ");
			tree.add(new Tree(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())));
		}
		
		for(int i = 0 ; i<K ; i ++) {
			// 봄 나이만큼 양분을 먹고 나이 +1 나이 어린애부터 양분 먹기
			spring();
			// 여름 죽은 나무들이 양분으로 바꾸기 /2
			summer();
			// 가을 5배수일때 8개 방향으로 1인 나무 생긴다 
			fall();
			// 겨울 양분이 plus만큼 추가하기 
			winter();
		}
		System.out.println(tree.size());
	}

	private static void winter() {
		// TODO Auto-generated method stub
		for(int i = 0 ; i<N ; i++) {
			for(int j = 0 ; j<N ; j++) {
				map[i][j] += plus[i][j];
			}
		}
	}

	private static void fall() {
		// TODO Auto-generated method stub
		int size = tree.size();
		for(int i = 0 ; i<size ; i++) {
			Tree cur = tree.poll();
			if(cur.age % 5 == 0 ) {
				for(int j = 0 ; j<8 ; j++) {
					int nx = cur.x + dx[j];
					int ny = cur.y + dy[j];
					if(0>nx || nx>=N || 0>ny || ny>=N) continue;
					
					tmp.add(new Tree(nx,ny,1));
				}
			}
			tmp.add(new Tree(cur.x,cur.y,cur.age));
		}
		// tmp에 있는거 다시 tree로 옮겨 담기 
		while(!tmp.isEmpty()) {
			tree.add(tmp.poll());
		}
	}

	private static void summer() {
		// TODO Auto-generated method stub
		while(!tree_dead.isEmpty()) {
			Tree cur = tree_dead.poll();
			map[cur.x][cur.y] += cur.age/2;
		}
	}

	private static void spring() {
		// TODO Auto-generated method stub
		int size = tree.size();
		for(int i = 0 ; i<size ; i ++) {
			Tree cur = tree.poll();
			//양분이 충분할 때 			
			if(map[cur.x][cur.y]>= cur.age) {
				map[cur.x][cur.y] -= cur.age;
				cur.age += 1;
				tmp.add(new Tree(cur.x,cur.y,cur.age));
			}
			else {
				tree_dead.add(new Tree(cur.x,cur.y,cur.age));
			}
		}
		while(!tmp.isEmpty()) {
			tree.add(tmp.poll());
		}
	}

}