백준 16235 나무 재테크(자바) - 구현

되게 간단한데 생각보다 계속 틀렸던 문제.

오류 원인

: 처음에 list를 PriorityQueue로 구성하여 알아서 정렬되도록 했는데 이렇게 하다보니 list를 for문으로 돌면서 체크하는 부분에서 그 뒤에 삽입되는 나이가 1인 나무들로 인해 내가 예상했던 순서대로 list에 들어있지 않아 오답이 계속 나왔다.

list를 ArrayList로 선언한 뒤 정렬해서 사용하는 것이 안전.

또, 죽은 나무가 있기 때문에 겨울이 끝나기 전에 새로운 list를 만들어 죽은 나무를 빼줘야 한다.

import java.util.*;

//1. 봄 : 나무가 나이만큼 양분 get, 나이 1 증가 // 여러개 나무 있다면 어린 나무부터 양분 get// 양분 부족해 나이만큼 못 먹으면 즉시 죽음
//2. 여름 : 봄에 죽은 나무가 양분으로// 죽은 나무마다 나이/2가 양분으로 추가됨(소수점 제외)
//3. 가을 : 나이가 5의 배수인 나무 인접 8칸에 나이1인 나무 생성
//4. 겨울 : 양분 추가
class Main {
    static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int[] dy = { -1, 0, 1, -1, 1, -1, 0, 1 };
    static class Tree implements Comparable<Tree>{
        int x,y,age;
        boolean dead;
        Tree(int x, int y, int age) {
            this.x = x;
            this.y = y;
            this.age = age;
        }

        @Override
        public int compareTo(Tree now) {
            return this.age - now.age;
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        ArrayList<Tree> list = new ArrayList<>();
        int[][] a = new int[n+1][n+1];
        int[][] nut = new int[n+1][n+1];
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                a[i][j] = sc.nextInt();
                nut[i][j] = 5;
            }
        }
        for (int i=0; i<m; i++) {
            list.add(new Tree(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
        while (k-->0) {
            Queue<Integer> die = new LinkedList<>();
            //봄
            Collections.sort(list);
            for (int i=0; i<list.size();i++) {
                Tree now = list.get(i);
                if (nut[now.x][now.y] >= now.age) {
                    nut[now.x][now.y] -= now.age;
                    now.age++;
                } else {
                    die.add(i);
                }
            }
            //여름
            while (!die.isEmpty()) {
                Tree now = list.get(die.poll());
                nut[now.x][now.y] += now.age/2;
                now.dead = true;
            }
            //가을
            Queue<Tree> autumn = new LinkedList<>();
            for (int i=0; i<list.size(); i++) {
                Tree now = list.get(i);
                if (now.dead) continue;
                if (now.age%5 ==0) {
                    autumn.add(now);
                }
            }

            ArrayList<Tree> newTree = new ArrayList<>();

            while (!autumn.isEmpty()) {
                Tree now = autumn.poll();
                for (int j=0; j<8; j++) {
                    int nx = now.x + dx[j];
                    int ny = now.y + dy[j];
                    if (nx<=0 || ny<=0 || nx>n || ny>n) continue;
                    newTree.add(new Tree(nx, ny, 1));
                }
            }

            for (Tree tree: list) {
                if (!tree.dead) {
                    newTree.add(tree);
                }
            }
            list = newTree;


            //겨울
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                    nut[i][j] += a[i][j];
                }
            }
        }
        System.out.println(list.size());
    }
}