[java]나무 재테크 - 백준16235

문제

• 나무 재테크(백준16235)

풀이

문제 해석을 하자면,

• K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구해야 하는 문제
• 단, 조건이 많고 시간초과도 조심해야하는 까다로운 문제이다.

풀이

• 입력좌표 (0,0) 으로 사용할거라 -1 임의로 추가했음
• 가장 처음에 양분은 모든 칸에 5만큼 들어있다는점 놓지지 말자
• “시간초과 해결방법” -> 주석 확인
  • 우선순위 큐 오버라이딩을 직접하는게 더 빠름(중요)
  • !qu.isEmpty() 보다 size 미리 구해서 사용하는게 더 빠름
  • 큐는 copyQu 만 계속 새로 할당하고, 2개의 큐를 번갈아가면서 낭비없이 사용(중요)
  • 문제에 적용은 안했는데 “큐” 사용할때 LinkedList 보다 ArrayDeque가 더 빠름

코드

public static int N, M, K;
	public static int[][] inMap = new int[12][12];
	public static int[][] foodMap = new int[12][12]; // 입력 양분
	public static PriorityQueue<Tree> qu = new PriorityQueue<>();
	public static PriorityQueue<Tree> copyQu;
	public static Queue<Tree> dieQu = new LinkedList<>(); // 죽은나무 기록
	public static int[] dx = {-1,-1,-1,0,0,1,1,1};
	public static int[] dy = {-1,0,1,-1,1,-1,0,1};
	// (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)
			
	public static void spring() {
//		copyQu = new PriorityQueue<>(Tree::compareTo); // 매번 새로 할당
		copyQu = new PriorityQueue<>(); // 매번 새로 할당
		int size = qu.size(); // !isEmpty 보다 더 빠른것 같음
		while(size-- > 0) {
			Tree t = qu.peek();
			qu.remove();
			int food = inMap[t.x][t.y];
			if(food < t.age) {
				dieQu.add(t);
				continue; // 못먹으면 사망
			}
			inMap[t.x][t.y]-=t.age;
			t.age+=1; // 먹으면 나이++
			copyQu.add(t);
		}
	}
	
	public static void summer() {
		int size = dieQu.size();
		while(size-- > 0) {
			Tree t= dieQu.peek();
			dieQu.remove();
			inMap[t.x][t.y]+=t.age/2; 
		}
	}
	
	public static void fall() {
		int size = copyQu.size();
		while(size-- > 0) {
			Tree t = copyQu.peek();
			copyQu.remove();
			if(t.age % 5 ==0) {
				// 번식
				for(int i=0; i<8; i++) {
					int nx = t.x+dx[i];
					int ny = t.y+dy[i];
					if(nx<0||ny<0||nx>=N||ny>=N) continue;
					qu.add(new Tree(nx, ny, 1)); // 번식나무 생성
				}
			}
			qu.add(t);
		}
	}
	
	public static void winter() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				inMap[i][j] += foodMap[i][j];
			}
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		K = Integer.parseInt(stk.nextToken());
		for(int i=0; i<N; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				inMap[i][j] = 5; // 초기값
				foodMap[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		for(int i=0; i<M; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(stk.nextToken())-1; // 좌표 0,0 으로 사용할거라 -1
			int y = Integer.parseInt(stk.nextToken())-1;
			int age = Integer.parseInt(stk.nextToken());
			qu.add(new Tree(x,y,age));
		}
		//run
		for(int i=0; i<K; i++) {
			//1.봄
			spring();
			//2.여름
			summer();
			//3.가을
			fall();
			//4.겨울	
			winter();
		}
		//output
		System.out.println(qu.size());
		
	}

//	static class Tree {
//		int x; int y; int age;
//		public Tree(int x, int y, int age) {
//			this.x=x; this.y=y; this.age=age;
//		}
//		
//		public int compareTo(Tree t) {
//			if(this.age < t.age) {
//				return -1;
//			}
//			return 1;
//		}
//	}
	
	static class Tree implements Comparable<Tree> {
	    int x, y, age;
	    
	    Tree(int x, int y, int age) {
	        this.x = x;
	        this.y = y;
	        this.age = age;
	    }
	    
	    public int compareTo(Tree t) {
	    	return Integer.compare(this.age, t.age);
	    }
	}

느낀점

생략