백준 16235번 : 나무 재테크

 문제

www.acmicpc.net/problem/16235

16235번: 나무 재테크

16235 나무 재테크

 

 구현 방법

 그대로 구현만 하면 문제이지만 계속 시간 초과가 났고 정렬을 한 번만 해도 된다는 사실을 알게 되었습니다.

반복문을 돌기 전 정렬을 한번 한 다음 돌면 그 후에 나이 순서가 바뀌는 일이 없기 때문에 더 이상의 정렬은 필요 없습니다.

1. 봄 - 나이를 먹어도 각자 다 1살씩 먹고 다시 그 순서대로 추가되기 때문에 나이 순서 바뀌지 않음

2. 여름 - 죽은 나무 큐를 사용하므로 나이 순서와 상관 없음

3. 가을 - 따로 나무를 보관할 큐를 생성하여 기존 나무들을 저장해주면 나이 순서대로 들어감. 새로운 나무를 기존에 있던 나무 큐에 모두 삽입한 다음 따로 보관 큐에 담긴 기존 나무들을 다시 나무 큐에 추가해줌 -> 새로운 나무들의 나이는 모두 1, 그 이후에 기존 나무들을 추가하면 나이 순서가 바뀌지 않음

 

 구현 코드

package BOJ.Gold;

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

public class BOJ16235_나무재테크 {
	static int N, M, K, size, nowR, nowC, nowAge;
	static int[][] field, addFood, deltas = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};;
	static Queue<Tree> trees, deadTrees, addTree;
	
	static class Tree implements Comparable<Tree> {
		int r, c, age;

		public Tree(int r, int c, int age) {
			super();
			this.r = r;
			this.c = c;
			this.age = age;
		}

		@Override
		public String toString() {
			return r+" "+c+" "+age;
		}

		@Override
		public int compareTo(Tree o) {
			return Integer.compare(this.age, o.age);
		}
	}
	
	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());
		field = new int[N][N]; // 땅
		addFood = new int[N][N]; // 매해 추가되는 양분
		for (int i=0;i<N;i++) {
			Arrays.fill(field[i], 5); // 초기 양분 5
		}
		
		for (int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0;j<N;j++) {
				addFood[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		trees = new LinkedList<>();
		deadTrees = new LinkedList<>();
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			trees.offer(new Tree(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())));
		}
		// 초기 설정 완료
		
		Collections.sort((List<Tree>)trees); // 정렬은 한번만
		
		for (int i=0;i<K;i++) {
			spring(); // 봄 : 나이 먹기
			summer(); // 여름 : 죽은 나무 양분으로 변함
			fall(); // 가을 : 나무 번식
			winter(); // 겨울 : 양분 추가
		}
		
		System.out.println(trees.size());
	}
	
	static void spring() {
		size = trees.size();
		for (int i=0;i<size;i++) {
			Tree now = trees.poll();
			if (field[now.r][now.c]>=now.age) { // 현재 땅의 양분이 나무 나이보다 많을 때
				field[now.r][now.c] -= now.age; // 나이 빼주고
				trees.offer(new Tree(now.r, now.c, now.age+1)); // 나이 +1 해서 다시 넣어주기
			} else deadTrees.offer(now); // 양분이 나이보다 더 적으면 나무는 죽음
		}
	}
	
	static void summer() {
		size = deadTrees.size();
		for (int i=0;i<size;i++) {
			Tree now = deadTrees.poll();
			field[now.r][now.c] += now.age/2; // 죽은 나무 나이/2를 해당 좌표 양분에 ++
		}
	}
	
	static void fall() {
		addTree = new LinkedList<>();
		size = trees.size();
		for (int i=0;i<size;i++) {
			Tree now = trees.poll();
			if (now.age%5==0) { // 나무의 나이가 5배수일 때
				for (int d=0;d<8;d++) {
					int nr = now.r+deltas[d][0];
					int nc = now.c+deltas[d][1];
					if (isIn(nr, nc)) trees.offer(new Tree(nr, nc, 1)); // 인접한 4방향에 나무 번식
				}
			}
			addTree.offer(now);
		}
		
		for (Tree tree : addTree) {
			trees.offer(tree);
		}
	}
	
	static void winter() {
		for (int i=0;i<N;i++) {
			for (int j=0;j<N;j++) {
				field[i][j] += addFood[i][j];
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<N && nc>=0 && nc<N;
	}
}

 

정답!