[BOJ] 16235. 나무 재테크 - Simultaion

[BOJ] 16235. 나무 재테크 - Simultaion

제출일 : 2019-10-15

문제 풀이 시간 : 2H

난이도 : ★★★☆

Problem

link : https://www.acmicpc.net/problem/16235

Input

첫째 줄에 K년이 지난 후 살아남은 나무의 수를 출력한다.

Output

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

Constraint

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

Example

input

5 2 4
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 3 2 3 2
2 1 3
3 2 3

output

13

Solution & Inpression

시뮬레이션 문제

문제에서 시키는데로 차근차근 풀게되면 어려움이 없는 문제지만

1*1 한칸에 여러 나무가 심어질수 있기때문에 자료구조를 어떻게 해야할지 고민을 하게 만든 문제였다.

처음 내가 생각한 자료구조는 ArrayList<Integer>[][]로 2차원 배열의 원소값이 ArrayList로 이루어진 자료구조를 선언하고 사용하려 했다.

하지만 다른 2차원 배열과 다르게 사용을 할 수 가 없었고, 모든 나무를 하나의 PriorityQueue에 모든 정보를 담아 문제를 풀었다.

Code

언어 : JAVA

메모리 : 165,300 kb

실행시간 : 1,532 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static int N, M, K;
    static int[][] robot, land;

    static PriorityQueue<Tree> tree;

    static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int[] dc = { -1, 0, 1, -1, 1, -1, 0, 1 };

    static class Tree implements Comparable<Tree> {
        int r, c, age;

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

        public int compareTo(Tree t) {
            return this.age > t.age ? 1 : -1;
        }

        public String toString() {
            return "(r=" + r + ", c=" + c + ", age=" + age + ")";
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt() + 1; // 땅의 크기 1base
        int M = sc.nextInt(); // 나무 수
        int K = sc.nextInt(); // 년 수
        robot = new int[N][N];
        land = new int[N][N];

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < N; j++) {
                robot[i][j] = sc.nextInt();// 로봇이 추가하는 양분
                land[i][j] = 5; // 초기 양분
            }
        }

        tree = new PriorityQueue<>();
        for (int i = 0; i < M; i++) {
            tree.offer(new Tree(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }
        ArrayList<Tree> dead = new ArrayList<>();
        ArrayList<Tree> alive = new ArrayList<>();
        for (int year = 0; year < K; year++) {
            // 봄
            while (!tree.isEmpty()) {
                Tree t = tree.poll();
                if (land[t.r][t.c] < t.age) {// 죽는다
                    dead.add(t);
                } else {
                    land[t.r][t.c] -= t.age; // 양분을 먹고
                    t.age++; // 한살도 먹고
                    alive.add(t);
                }
            }

            // 여름
            for (int i = 0; i < dead.size(); i++) {
                Tree t = dead.get(i);
                // 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다
                land[t.r][t.c] += t.age / 2;
            }
            dead.clear();

            // 가을
            for (int i = 0; i < alive.size(); i++) {
                Tree t = alive.get(i);
                if (t.age % 5 != 0) {// 번식하지 못하는 나무
                    tree.offer(t);
                } else {
                    tree.offer(t);
                    for (int k = 0; k < 8; k++) {
                        int r = t.r + dr[k];
                        int c = t.c + dc[k];
                        if (1 <= r && r < N && 1 <= c && c < N) {
                            Tree nt = new Tree(r, c, 1);
                            //System.out.println("    " + nt);
                            tree.offer(nt);
                        }
                    }
                }
            }
            alive.clear();

            // 겨울
            for (int i = 1; i < N; i++) {
                for (int j = 1; j < N; j++) {
                    land[i][j] += robot[i][j];
                }
            }
        }
        System.out.println(tree.size());

    }
}