22 Mar 2023

[Java] 백준 16235번: 나무 재테크

16235

풀이 방법

푸는 데 정말 오래 걸렸던 문제이다.

나무의 정보는 배열의 최초 인덱스인 (0,0) 이 아닌 (1,1) 부터 들어오기 때문에 배열을 [N+1][N+1]로 선언하였는데, 마지막 겨울 영양소 추가 부분에서 이중for문을 0 부터 시작해 버리는 바람에 계속 틀렸습니다가 떴다. 8개의 테케는 다 맞았는데 말이다!!!

인덱스를 수정하고 다시 돌렸는데, 처음에는 리스트로 구현하였더니 while(k-- > 0) 이 한번 돌 때마다 정렬을 다시 해줘야 했고, 최대 1000년동안 나무 하나가 번식하면 8개가 추가로 생기기 때문에 시간초과가 나기 딱 좋았다. 결국은 Deque를 사용하여서 다음과 같이 풀었다.

처음의 Deque인 plantedTree는 입력받은 나무를 나이 기준으로 오름차순 정렬하였다.
봄에는 plantedTree.poll()로 요소를 뺀 다음 나이대로 영양분을 먹인다.
- 먹었으면 다시 plantedTree의 마지막 요소로 들어간다.
- 영양분을 못 먹으면 deadTree에서 영양분이 되기를 기다린다.
- 영양분을 먹어 나이가 5의 배수가 되었을 때는 번식을 위해 bornTree에도 추가한다.
여름에는 DeadTree의 나무 친구들이 영양분이 된다.
가을에는 BornTree의 나무들의 주위 8칸에 애기나무가 심어지는데, 나이 순 정렬을 위해 plantedTree의 앞부분에 추가된다.
겨울에는 영양소가 추가된다(인덱스 헷갈리지 말자.)

풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16235_나무_재테크 {
	static class Tree implements Comparable<Tree>{
		int r;
		int c;
		int age;
		
		Tree(int r, int c, int age) {
			this.r = r;
			this.c = c;
			this.age = age;
		}

		@Override
		public int compareTo(Tree t) {
			return this.age - t.age;
		}

		@Override
		public String toString() {
			return "Tree [r=" + r + ", c=" + c + ", age=" + age + "]";
		}

	}
	static int[] DR = {-1,-1,-1,0,0,1,1,1};
	static int[] DC = {-1,0,1,-1,1,-1,0,1};
	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()); // NxN 사이즈 맵
		int M = Integer.parseInt(st.nextToken()); // 심은 나무의 정보(위치x, 위치y, 나이)
		int K = Integer.parseInt(st.nextToken()); // K년 지난 후
		int[][] soil = new int[N+1][N+1];
		int[][] nutrition = new int[N+1][N+1];
		
		ArrayList<Tree> inputTree = new ArrayList<>();
		Deque<Tree> plantedTree = new ArrayDeque<>();
		Queue<Tree> bornTree = new LinkedList<>();
		Queue<Tree> deadTree = new LinkedList<>();
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) {
				nutrition[i][j] = Integer.parseInt(st.nextToken());
				soil[i][j] = 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());
			inputTree.add(new Tree(x, y, age));
		}
		
		Collections.sort(inputTree);
		for(Tree t : inputTree) {
			plantedTree.addLast(t);
		}

		while(K-- > 0) {
			// 봄 (양분 먹고 나이 1 증가)
			int qSize = plantedTree.size();
			for(int i=0; i<qSize; i++) {
				Tree curTree = plantedTree.pollFirst();
				
				if(soil[curTree.r][curTree.c] >= curTree.age) {
					soil[curTree.r][curTree.c] -= curTree.age;
					curTree.age++;
					if(curTree.age % 5 == 0) bornTree.add(curTree);
					plantedTree.addLast(curTree);
				} else {
					deadTree.add(new Tree(curTree.r, curTree.c, curTree.age));
				}
			}
			
			// 여름 (죽은 나무가 양분으로 변함)
			while(!deadTree.isEmpty()) {
				Tree dead = deadTree.poll();
				
				soil[dead.r][dead.c] += dead.age/2;
			}
			
			// 가을 (나무 번식)
			while(!bornTree.isEmpty()) {
				Tree born = bornTree.poll();
				
				for(int i=0; i<8; i++) {
					int nr = born.r + DR[i];
					int nc = born.c + DC[i];
					
					if(nr>=1 && nr<=N && nc>=1 && nc<=N) {
						plantedTree.addFirst(new Tree(nr, nc, 1));
					}
				}
			}
			
			// 겨울(영양소 추가)
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					soil[i][j] += nutrition[i][j];
				}
			}
		}
	
		System.out.println(plantedTree.size());
	}
}

Thank You For Reading

점점 강해지고 있습니다.