[백준 Baekjoon] 16235번 나무 재테크 - JAVA

백준 Baekjoon 16235번 나무 재테크 - JAVA

---

문제 풀이

구현, 시뮬레이션으로 분류된 문제이다. 문제 설명을 잘 읽고 정리하여 따라 하는것으로 풀 수 있다. 풀이에 대한 설명보다 코드의 주석을 보는것이 이해가 쉬룰 것이다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // N x N 크기의 땅
        int M = Integer.parseInt(st.nextToken()); // M개의 나무
        int K = Integer.parseInt(st.nextToken()); // K년

        int[][] food = new int[N][N]; // 양분
        int[][] A = new int[N][N]; // 추가되는 양분의 양
        PriorityQueue<Integer>[][] tree = new PriorityQueue[N][N];

        for (int i = 0; i < N; i++) {
            // 가장 처음에 양분은 모든 칸에 5만큼 들어있다.
            Arrays.fill(food[i], 5);

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int z = Integer.parseInt(st.nextToken());

            // 나이가 어린 나무부터 양분을 먹는다.
            tree[x][y].add(z);
        }

        int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
        int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};

        while (K-- > 0) {
            Queue<int[]> breed = new LinkedList<>();

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    /* 봄 */
                    PriorityQueue<Integer> after_eat = new PriorityQueue<>();

                    // 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다.
                    // 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
                    while (!tree[i][j].isEmpty() && food[i][j] - tree[i][j].peek() >= 0) {
                        int young_tree = tree[i][j].poll();

                        // 봄에는 나무가 자신의 나이만큼 양분을 먹고,
                        food[i][j] -= young_tree;
                        // 나이가 1증가한다.
                        after_eat.add(young_tree + 1);

                        if ((young_tree + 1) % 5 == 0) { // 번식할 나무 개수
                            breed.add(new int[]{i, j});
                        }
                    }
                    /* */

                    /* 여름 */
                    // 여름에는 봄에 죽은 나무가 양분으로 변하게 된다.
                    while (!tree[i][j].isEmpty()) {
                        // 각각의 죽은 나무마다 나이를 2로 나눈값이 나무가 있던 칸에 양분으로 추가된다.
                        food[i][j] += tree[i][j].poll() / 2;
                    }
                    /* */

                    tree[i][j] = after_eat;

                    /* 겨울 */
                    // 겨울에는 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.
                    food[i][j] += A[i][j];
                    /* */
                }
            }

            /* 가을 */
            // 가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며
            while (!breed.isEmpty()) {
                int[] pos = breed.poll();

                // 인접 8개의 칸에 나이가 1인 나무가 생긴다.
                for (int k = 0; k < 8; k++) {
                    int nx = pos[0] + dx[k];
                    int ny = pos[1] + dy[k];

                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                    tree[nx][ny].add(1);
                }
            }
            /* */
        }

        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                answer += tree[i][j].size();
            }
        }
        System.out.println(answer);
    }
}