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

문제 - (https://www.acmicpc.net/problem/16235)

구현 자체는 어렵지 않은 시뮬레이션 문제였다

문제를 풀면서 이게 골드 4라고?라고 생각할 정도였으니,...

근데 채점을 해보니 바로 시간초과가 났다.

이 문제의 키포인트는 어떻게 시간초과가 나지 않게 시뮬레이션을 돌릴 것인지 인 것 같다.

 

앞으로의 코딩에서도 그렇고 꼭 알고 넘어가야 할 것이 있어서 블로그에 포스팅하기로 했다.

 

처음에 자꾸 시간초과가시간 초과가 떴을 때 어디가 문젠지 몰라서 시간 초과가 날만한 곳을 예상하고 수정해서 제출하기를 반복했다.

- 죽은 나무를 큐에 담아서 시간초과가 났나? => 아님. 큐의 offer, poll은 O(1)이다.

- remove할 때 시간 복잡도가 큰가? => 아님. LinkedList에서 Iterator를 통한 remove는 O(1)이다.

- 가을에 새로운 나무를 추가할 때 for문을 사용해서 느린 건가? => 정답!!!

LinkedList의 경우 순회를 할때 for문보다 for-each문이 훨씬 빠르다.

 

밑에 코드를 보면 알 수 있겠지만,

주석처리한 부분은 일반 for문을 사용하고 trees 리스트에 addFirst로 번식한 나무들을 추가하는 방법을 택했다.

하지만 이 코드보다

babyTrees라는 일종의 temp리스트를 '생성'하고 for-each문으로 순회하면서 번식할 나무를 babyTrees에 담고

순회가 끝난 뒤 원래의 trees리스트에 babyList를 더해주는 과정이 수행 시간이 짧은 것을 알 수 있다.

나는 new연산을 통해 무언가를 생성하면 수행시간이 더 안 좋을 줄 알았는데,

경우에 따라선 for문을 사용하는 것이 수행시간에 더 큰 영향을 끼칠 수 있다는 것을 알 수 있었다.

---

📌주의할 점

• LinkedList의 경우 순회를 할때 for문보다 for-each문이 훨씬 빠르다.
• 큐의 offer,poll은 O(1)
• LinkedList에서 Iterator를 통한 remove는 O(1) 
• List에서 삭제 연산은 안전하고 빠른 iterator를 통해 진행하자!! 그렇지 않으면 ModificationException를 만날 수 있다.

 

---

코드

package algorithm.baekjoon.samsungA;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 골드 4 - 나무 재테크
 */
public class _16235_TreeFinTech {
    static int n, m, k;
    static int[][] map;
    static int[][] yangboon;
    static int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1};
    static LinkedList<Tree> trees;
    static Queue<Tree> dead;
    static int year;

    static class Tree {
        int x;
        int y;
        int age;

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

    static void simulate() {
        while (true) {
            if (year == k) return;

            // 봄
            Iterator<Tree> iterator = trees.iterator();
            while (iterator.hasNext()) {
                Tree tree = iterator.next();
                int r = tree.x;
                int c = tree.y;
                int age = tree.age;
                if (map[r][c] - age < 0) {
                    // 먹지못하고 즉시 죽음
                    dead.offer(tree);
                    iterator.remove(); /* LinkedList에서 iterator를 통한 remove : O(1) */
                } else {
                    map[r][c] -= age;
                    tree.age += 1;
                }
            }

            // 여름
            while (!dead.isEmpty()) {
                Tree tree = dead.poll();
                map[tree.x][tree.y] += tree.age / 2;
            }

            // 가을
            /* 시간 지연 사유 : for문 사용 */
//            for (int i = 0; i < trees.size(); i++) {
//                Tree tree = trees.get(i);
//                int r = tree.x;
//                int c = tree.y;
//                if (tree.age % 5 != 0) continue;
//                for (int d = 0; d < 8; d++) {
//                    int nr = r + dr[d];
//                    int nc = c + dc[d];
//                    if (nr < 1 || nc < 1 || nr > n || nc > n) continue;
//                    trees.addFirst(new Tree(nr, nc, 1));
//                    i++;
//                }
//            }

            LinkedList<Tree> babyTrees = new LinkedList<>();
            for (Tree tree : trees) {
                int r = tree.x;
                int c = tree.y;
                if (tree.age % 5 != 0) continue;
                for (int d = 0; d < 8; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr < 1 || nc < 1 || nr > n || nc > n) continue;
                    babyTrees.add(new Tree(nr, nc, 1));
                }
            }
            /* LinkedList에서 addAll : O(1) */
            trees.addAll(0, babyTrees);

            // 겨울
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    map[i][j] += yangboon[i][j];
                }
            }

            year++;
        }
    }

    public static void main(String[] args) throws Exception {
        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());

        map = new int[n + 1][n + 1]; // 1부터 시작
        yangboon = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = 5;
                yangboon[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        trees = new LinkedList<>();
        dead = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            trees.add(
                    new Tree(
                            Integer.parseInt(st.nextToken()),
                            Integer.parseInt(st.nextToken()),
                            Integer.parseInt(st.nextToken())
                    )
            );
        }

        year = 0;

        simulate();

        System.out.println(trees.size());
    }
}