BOJ - 16235 ) 나무 재테크

 

 

---

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

16235번: 나무 재테크

 

---

할짓없는 친구가 NXN 땅을 사서 나무를 키우는 문제이다. 로봇도 사서 매년 겨울에 양분도 주고,

각 계절마다 설명대로의 작업을 거치게 되는데, 

 

설명을 이해하니 큐2개로 해결될것 같았다. 막상 구현하다보니 죽은 나무를 관리하는 큐를 하나더 썼지만..

 

우선순위큐로 한번해봤는데 터져서 덱으로 바꾸어 보았더니 통과해버렸다..

 

그냥 문제 조건대로 코딩해주면 된다.

 

---

 

package 풀문제;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_나무재테크 {
	
	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 Nutri_map[][] = new int[n+1][n+1];
		int Robot_map[][] = new int[n+1][n+1];
		int dirx[] = {1,1,-1,-1,0,0,-1,1};
		int diry[] = {1,-1,1,-1,1,-1,0,0};
		
		ArrayDeque<int [] > dq = new ArrayDeque<>();
		ArrayDeque<int [] > dq2 = new ArrayDeque<>();
		ArrayDeque<int []> dead = new ArrayDeque<>();
		
		for(int y= 1 ; y <= n ; y ++) {
			st = new StringTokenizer(br.readLine());
			for(int x= 1 ; x <= n ; x++) {
				Robot_map[y][x] = Integer.parseInt(st.nextToken());
				Nutri_map[y][x] = 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 age = Integer.parseInt(st.nextToken());
			dq.add(new int[] {age,x,y});
		}
		
		for(int year = 1 ; year <= k ; year++) {
			// 봄
			while(!dq.isEmpty()) {
				int now[] = dq.poll();
				int age = now[0];
				int y = now[1] , x = now[2];
				if(Nutri_map[y][x] < age) {
					dead.add(new int[] {age, y,x});
					continue;
				}
				Nutri_map[y][x] -= age;
				dq2.add(new int[] {age+1,y,x});
			}
			// 여름
			while(!dead.isEmpty()) {
				int now[] = dead.poll();
				Nutri_map[now[1]][now[2]] += (now[0]/2);
			}
			// 가을
			while(!dq2.isEmpty()) {
				int now[] = dq2.poll();
				int y = now[1] , x = now[2];
				int age = now[0];
				if( (age % 5) ==0) {
					for(int index = 0 ; index < 8 ; index++) {
						int ny= y + diry[index];
						int nx= x + dirx[index];
						if(ny >= 1 && nx>=1 && ny <= n && nx <= n) {
							dq.addFirst(new int[] {1,ny,nx});
						}
					}
				}
				dq.add(new int[]{age,y,x});
			}
			
			// 겨울
			for(int y = 1 ; y <= n ; y++) {
				for(int x = 1 ; x<= n ; x++) {
					Nutri_map[y][x] += Robot_map[y][x];
				}
			}
		}
		System.out.print(dq.size());
	}
}

 

---

우선순위 큐쓰니까 37%에서 터져버렸다.. Deque짱!

 

그래서 좀 우선순위 큐를 조금만? 쓰도록 조정했더니

우선순위큐로도 통과가 가능했다..

 

하지만 문제 시간보가 훨씬 넘었고,, 찾아보니 우선순위 큐는 내부적으로 맥스힙구조이기 때문에

, Searching에 O(1)이 안걸릴수있다고한다..