[BOJ/Java] 나무 재테크 (16235)

나무 재테크 (16235)

1. 문제 분석

문제 개요

• 나무 재테크 문제는 N x N 크기의 땅에 나무를 심고, 주어진 조건에 따라 나무를 키워나가며, K년이 지난 후 살아남은 나무의 개수를 구하는 문제이다.
• 계절에 따라 나무의 성장, 죽음, 번식, 그리고 땅의 양분이 추가되는 과정이 주어지며, 이를 시뮬레이션으로 해결해야 한다.

입력 형식

1. 첫 번째 줄에는 N(땅의 크기), M(처음 심어진 나무의 개수), K(몇 년 후까지 볼 것인지) 주어진다.
2. 그다음 N개의 줄에 각 칸에 추가되는 양분의 양이 주어진다.
3. 그다음 M개의 줄에 나무의 위치와 나이 정보가 주어진다.

출력 형식

• K년 후에 살아남은 나무의 개수를 출력한다.

2. 알고리즘 종류

• 시뮬레이션: 계절별로 주어진 규칙에 따라 나무의 상태를 변화시켜 시뮬레이션을 진행한다.
• 우선순위 큐(Priority Queue): 나이가 어린 나무가 먼저 양분을 흡수해야 하므로, 나무의 나이를 기준으로 정렬이 필요하다.

3. 주요 부분 및 코드 작성 방법

1. 초기화

• 땅의 크기 N, 나무의 개수 M, 몇 년 동안 진행할 것인지 K를 입력받는다.
• 각 칸에 추가되는 양분의 양을 입력받고, 처음에 모든 칸의 양분을 5로 초기화한다.

2. 나무의 성장 및 죽음

• 봄: 각 나무는 자신의 나이만큼 땅의 양분을 먹고 나이가 1씩 증가한다. 만약 나무가 충분한 양분을 얻지 못하면 그 나무는 죽는다.
• 여름: 봄에 죽은 나무들은 양분이 되어 그 자리에 다시 반환된다. 죽은 나무의 나이 절반만큼 양분이 추가된다.

3. 나무의 번식

• 가을: 나무의 나이가 5의 배수인 경우, 인접한 8방향에 새로운 나무가 생긴다. 번식된 나무는 나이가 1이다.

4. 양분 추가

• 겨울: 각 칸에 주어진 양분을 추가한다.

4. 코드 설명

(1) 메인 함수 (main)

• 초기화 및 입력 처리

    N = Integer.parseInt(st.nextToken());  // 땅의 크기
    M = Integer.parseInt(st.nextToken());  // 나무의 개수
    K = Integer.parseInt(st.nextToken());  // 몇 년 동안 진행할지

  • 땅의 크기 N, 나무의 개수 M, 몇 년 동안 진행할지 K를 입력받는다.

• 땅의 양분 정보 및 나무 정보 입력

    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());  // 추가될 양분의 양
            grid[i][j] = 5;  // 초기 양분은 5
        }
    }
   
    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());  // 나무의 나이
        plant.add(new Tree(x, y, z));  // 나무 리스트에 추가
    }

  • A 배열에 양분 정보를 입력받고, 각 칸의 초기 양분을 5로 설정한다.
  • 나무의 위치와 나이를 받아 Tree 객체로 저장한다.

• 시뮬레이션 실행

    for (int i = 0; i < K; i++) {
        spring();  // 봄
        summer();  // 여름
        fall();    // 가을
        winter();  // 겨울
        Collections.sort(plant, (o1, o2) -> o1.age - o2.age);  // 나이순으로 정렬
    }
    System.out.println(plant.size());  // K년 후 살아남은 나무의 개수 출력

  • K년 동안 봄, 여름, 가을, 겨울의 시뮬레이션을 차례로 실행한다.

(2) 계절별 함수 구현

• spring 함수: 봄에는 나무가 자신의 나이만큼 양분을 먹고 나이가 1씩 증가한다. 만약 양분이 부족하면 그 나무는 죽는다.

    public static void spring() {
        for (int i = 0; i < plant.size(); i++) {
            Tree tree = plant.get(i);
            if (grid[tree.x][tree.y] < tree.age) {  // 양분 부족하면 나무 죽음
                deadTree.add(i);  // 죽은 나무 인덱스 저장
            } else {
                grid[tree.x][tree.y] -= tree.age;  // 양분 흡수
                tree.age++;  // 나이 증가
            }
        }
    }

• summer 함수: 여름에는 죽은 나무가 양분이 되어 땅에 반환된다.

    public static void summer() {
        while (!deadTree.isEmpty()) {
            Tree tree = plant.get(deadTree.poll());  // 죽은 나무 처리
            grid[tree.x][tree.y] += (tree.age / 2);  // 죽은 나무가 양분으로 변환
            tree.deadTree = true;  // 나무 상태를 죽은 나무로 표시
        }
    }

• fall 함수: 가을에는 나무가 번식한다. 나이가 5의 배수인 나무는 인접한 8방향으로 번식한다.

    public static void fall() {
        for (int i = 0; i < plant.size(); i++) {
            Tree tree = plant.get(i);
            if (tree.deadTree) continue;  // 죽은 나무는 번식하지 않음
            if (tree.age % 5 == 0) {  // 나이가 5의 배수인 나무 번식
                for (int d = 0; d < 8; d++) {
                    int nr = tree.x + dr[d];
                    int nc = tree.y + dc[d];
                    if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;  // 범위 체크
                    plant.add(new Tree(nr, nc, 1));  // 새로운 나무 추가
                }
            }
        }
   
        // 죽은 나무 제거
        ArrayList<Tree> newTree = new ArrayList<>();
        for (Tree tree : plant) {
            if (tree.deadTree) continue;
            newTree.add(tree);
        }
        plant = newTree;
    }

• winter 함수: 겨울에는 각 칸에 주어진 양분을 추가한다.

    public static void winter() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] += A[i][j];  // 추가 양분 더함
            }
        }
    }

5. 전체 코드

package BOJ.Day0924.BOJ나무_재테크;
 
import java.io.*;
import java.util.*;
 
public class BOJ16235 {
    static int N, M, K;  // 땅의 크기, 나무의 개수, 몇 년 동안 진행할지
    static int[][] grid, A;  // 땅의 양분 상태, 추가 양분 정보
    static ArrayList<Tree> plant = new ArrayList<>();  // 나무 리스트
    static Queue<Integer> deadTree = new LinkedList<>();  // 죽은 나무의 인덱스
    static int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1};  // 8방향
    static int[] dc = {0, 0, -1, 1, -
 
1, 1, -1, 1};
 
    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());  // 땅의 크기
        M = Integer.parseInt(st.nextToken());  // 나무의 개수
        K = Integer.parseInt(st.nextToken());  // 몇 년 동안 진행할지
        grid = new int[N][N];
        A = new int[N][N];
 
        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());  // 추가 양분 정보
                grid[i][j] = 5;  // 처음 땅의 양분은 5
            }
        }
 
        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());  // 나무의 나이
            plant.add(new Tree(x, y, z));  // 나무 추가
        }
        Collections.sort(plant, (o1, o2) -> o1.age - o2.age);  // 나이순으로 정렬
 
        for (int i = 0; i < K; i++) {
            spring();  // 봄
            summer();  // 여름
            fall();    // 가을
            winter();  // 겨울
            Collections.sort(plant, (o1, o2) -> o1.age - o2.age);  // 나이순으로 재정렬
        }
        System.out.println(plant.size());  // K년 후 살아남은 나무의 개수 출력
    }
 
    // 봄: 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가한다. 양분이 부족하면 죽는다.
    public static void spring() {
        for (int i = 0; i < plant.size(); i++) {
            Tree tree = plant.get(i);
            if (grid[tree.x][tree.y] < tree.age) {  // 양분이 부족하면
                deadTree.add(i);  // 죽은 나무 인덱스 추가
            } else {
                grid[tree.x][tree.y] -= tree.age;  // 양분 흡수
                tree.age++;  // 나이 증가
            }
        }
    }
 
    // 여름: 죽은 나무가 양분이 되어 땅으로 돌아간다.
    public static void summer() {
        while (!deadTree.isEmpty()) {
            Tree tree = plant.get(deadTree.poll());  // 죽은 나무 처리
            grid[tree.x][tree.y] += (tree.age / 2);  // 죽은 나무의 나이 절반이 양분으로 변환
            tree.deadTree = true;  // 나무 상태를 죽은 나무로 표시
        }
    }
 
    // 가을: 나이가 5의 배수인 나무가 번식한다.
    public static void fall() {
        for (int i = 0; i < plant.size(); i++) {
            Tree tree = plant.get(i);
            if (tree.deadTree) continue;  // 죽은 나무는 번식하지 않음
            if (tree.age % 5 == 0) {  // 나이가 5의 배수인 나무 번식
                for (int d = 0; d < 8; d++) {
                    int nr = tree.x + dr[d];
                    int nc = tree.y + dc[d];
                    if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;  // 범위 체크
                    plant.add(new Tree(nr, nc, 1));  // 새로운 나무 추가
                }
            }
        }
 
        // 죽은 나무 제거
        ArrayList<Tree> newTree = new ArrayList<>();
        for (Tree tree : plant) {
            if (tree.deadTree) continue;
            newTree.add(tree);
        }
        plant = newTree;
    }
 
    // 겨울: 각 칸에 주어진 양분을 추가한다.
    public static void winter() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] += A[i][j];  // 양분 추가
            }
        }
    }
}
 
// 나무 클래스
class Tree {
    int x, y, age;
    boolean deadTree;  // 나무가 죽었는지 여부
 
    Tree(int x, int y, int age) {
        this.x = x;
        this.y = y;
        this.age = age;
    }
}