16235. 나무 재테크

문제

[BOJ-16235] 나무 재테크

---

문제 해결 아이디어

시뮬레이션인데 이제 자료구조를 곁들인..🥲

조건

1 ≤ $N$ ≤ 10
1 ≤ $M$ ≤ $N^2$
1 ≤ $K$ ≤ 1,000
1 ≤ $A[r][c]$ ≤ 100
1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
입력으로 주어지는 나무의 위치는 모두 서로 다름

주어진 조건의 크기가 별로 크지 않아서 단순 시뮬레이션이라고 생각했었다.. (시간초과 어마무시..)

LinkedList 접근

• Tree 리스트를 매년 정렬 하는데 O(n log n) 걸린다.. 그래서 처음 입력받은 나무들 한 번만 정렬
• 가을에 맨 앞에 나이 1인 친구들을 삽입하면 정렬할 필요가 없기 때문에, 맨 앞 삽입이 O(1)인 LinkedList 사용 (ArrayList는 O(n))

봄

• Tree 리스트 순회하면서 해당 땅에 양분이 나무 나이보다 크거나 같으면 한 살 더 먹고, 아니면 죽는다..!

여름

• Tree 리스트 순회시 Iterator를 사용하면 한 번 순회 만으로 바로 Tree리스트에 죽은 나무들을 제거해준다!! (반복 횟수 줄이는데 용이)

가을

• Tree 리스트 순회 하면서, 번식하여 생긴 한 살인 애기 나무들을 바로 Tree 리스트에 삽입하면 forEach로 순회해서 문제가 있고, 또 정렬해줘야한다..!
• 그래서 따로 애기들용 Tree 리스트에다가 삽입 후, addAll 메소드로 기존 Tree 리스트에 맨 앞에 삽입 (정렬 필요x)

겨울

• 그저 양분 공급

---

코드

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

public class Solution16235 {
    static int N, M, K;
    static int[][] A, B;
    static int x, y, z;
    static List<Tree> trees;
    static int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
    static int[] dy = {1, -1, 0, 0, 1, -1, 1, -1};
    static int treeCnt;

    static class Tree implements Comparable<Tree> {
        int x;
        int y;
        int age;
        boolean isAlive;

        Tree(int x, int y, int age, boolean isAlive) {
            this.x = x;
            this.y = y;
            this.age = age;
            this.isAlive = isAlive;
        }

        @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()); // N*N 땅
        M = Integer.parseInt(st.nextToken()); // M 그루
        K = Integer.parseInt(st.nextToken()); // K 년 후
        A = new int[N][N]; // 겨울에 추가될 양분
        B = new int[N][N]; // 내 땅 양분


        trees = new LinkedList<>();
        treeCnt = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
                B[i][j] = 5;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken()); // 나무 x좌표
            y = Integer.parseInt(st.nextToken()); // 나무 y좌표
            z = Integer.parseInt(st.nextToken()); // 나무 나이 z
            trees.add(new Tree(x-1, y-1, z, true));
        }
        Collections.sort(trees);

        for (int k = 1; k <= K; k++) { // 나이별 나무 (오름차순)

            // 봄
            for (Tree tree : trees) {
                if (B[tree.x][tree.y] >= tree.age && tree.isAlive) {
                    B[tree.x][tree.y] -= tree.age;
                    tree.age += 1;
                } else {
                    tree.isAlive = false;
                }
            }

            // 여름
            Iterator<Tree> iter = trees.iterator();
            while (iter.hasNext()) {
                Tree tree = iter.next();
                if (!tree.isAlive) {
                    B[tree.x][tree.y] += tree.age / 2; // 죽은나무 양분
                    iter.remove();
                }
            }

            // 가을
            List<Tree> newTrees = new LinkedList<>(); 
            for (Tree tree : trees) {
                if (tree.age % 5 == 0 && tree.isAlive) {
                    for (int d = 0; d < 8; d++) {
                        int nx = tree.x + dx[d];
                        int ny = tree.y + dy[d];
                        if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                        newTrees.add(0, new Tree(nx, ny, 1, true));
                    }
                }
            }
            trees.addAll(0, newTrees);

            // 겨울
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    B[i][j] += A[i][j];
                }
            }
        }
        
        for (Tree tree : trees) {
            if (tree.isAlive) {
                treeCnt += 1;
            }
        }
        System.out.println(treeCnt);
    }
}