알고리즘
[Java] 백준 16235번 나무 재테크
J3SUNG
2023. 2. 10. 20:45
728x90
N년이 지났을 때 나무의 수를 구하는 시뮬레이션 문제입니다.
봄, 여름, 가을, 겨울이 있으며 차례대로 진행됩니다.
봄 - 나무가 자리에 있는 양분을 먹습니다.(어린 나무부터 순서대로) (나이만큼 못먹으면 죽은 나무가됨)
여름 - 죽은 나무는 자리에 나이/2를 양분으로 남깁니다. (소숫점 버림)
가을 - 나무의 나이가 5배수일때 8방향으로 나이가 1인 나무를 생성합니다
겨울 - 입력으로 받은 양분을 땅에 추가해줍니다.
위의 작업들을 N년동안 반복한 후 나무의 수를 출력해주면 됩니다.
우선순위 큐를 사용해서 어린나무를 뽑아주었었는데 시간초과가 발생했습니다.
그래서 처음에 한번만 정렬을 해주고 Queue를 통해서 나무들의 정보를 저장했습니다.
죽은나무와 아기나무가 생성될때 새로운 배열과 순서를 조정해서 정렬을 하지 않아도 되게 만들었습니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
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[][] nutrients = new int[n][n];
int[][] map = new int[n][n];
int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
Tree[] arr = new Tree[m];
// PriorityQueue<Tree> trees = new PriorityQueue<>((o1, o2) -> (o1.y==o2.y ? (o1.x==o2.x ? o1.z-o2.z : o1.x-o2.x) : o1.y-o2.y));
Queue<Tree> trees = new LinkedList<>();
Queue<Tree> temp = new LinkedList<>();
Queue<Tree> babyTree = new LinkedList<>();
Queue<Tree> deadTrees = new LinkedList<>();
for(int i=0; i<n; ++i) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; ++j) {
map[i][j] = 5;
nutrients[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=0; i<m; ++i) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken()) - 1;
int z = Integer.parseInt(st.nextToken());
arr[i] = (new Tree(x, y, z));
// trees.add(new Tree(x, y, z));
}
Arrays.sort(arr, (o1, o2) -> (o1.y==o2.y ? (o1.x==o2.x ? o1.z-o2.z : o1.x-o2.x) : o1.y-o2.y));
for(int i=0; i<m; ++i) {
trees.add(arr[i]);
}
for(int y=0; y<k; ++y) {
while(!trees.isEmpty()) {
Tree t = trees.poll();
if(map[t.y][t.x] >= t.z) {
map[t.y][t.x] -= t.z;
++t.z;
temp.add(t);
} else {
deadTrees.add(t);
}
}
while(!temp.isEmpty()) {
trees.add(temp.poll());
}
while(!deadTrees.isEmpty()) {
Tree t = deadTrees.poll();
map[t.y][t.x] += (t.z/2);
}
while(!trees.isEmpty()) {
Tree t = trees.poll();
temp.add(t);
if(t.z % 5 == 0) {
for(int i=0; i<8; ++i) {
if(t.y + dy[i] < 0 || t.x + dx[i] < 0 || t.y + dy[i] >= n || t.x + dx[i] >= n) {
continue;
}
babyTree.add(new Tree(t.x + dx[i], t.y + dy[i], 1));
}
}
}
while(!babyTree.isEmpty()) {
trees.add(babyTree.poll());
}
while(!temp.isEmpty()) {
trees.add(temp.poll());
}
for(int i=0; i<n; ++i) {
for(int j=0; j<n; ++j) {
map[i][j] += nutrients[i][j];
}
}
}
bw.write(trees.size() + "");
bw.close();
}
static class Tree {
int x;
int y;
int z;
public Tree(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
}
}