[백준 16235] 나무 재테크(Java)

문제 링크 : https://www.acmicpc.net/problem/16235

이 문제는 문제에 주어진 조건대로 하나하나 구현하면 됩니다.

이 문제의 포인트는 어떻게 어린 나무들을 먼저 양분을 먹게 할 것인지를 체크하는 것입니다. 저는 우선순위 큐를 나이를 기준으로 정렬되게끔 구현하여 데이터 삽입 시 자동적으로 정렬되도록 구현하였습니다. 이 때 주의할 점은 큐의 사이즈를 기준으로 반복문을 돌릴 경우 큐의 데이터가 poll되어 사이즈의 변동이 발생하기 때문에 별도의 리스트를 할당하여 데이터를 임시로 추가한 후 모든 로직이 완료된 후 해당 데이터를 추가하면 됩니다.

또한 이 문제의 가장 큰 주의점 중 하나는 입력 좌표를 굉장히 잘 봐야 한다는 것입니다. 문제에는 나무의 정보를 나타내는 세 정수 x, y, z가 주어진다. 라고 적혀있습니다. 하지만 만약 입력을 x,y,z 로 받고 이차원 배열을 A[세로][가로] 로 설정할 경우 오류가 발생합니다. 이는 문제에서 말하는 나무의 위치 (x, y) 값이 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수 에 대응한다고 보면 x가 세로, y가 가로 라는 이상한 방식으로 입력을 받아야 합니다. 이 부분을 반드시 주의해서 푸셔야 합니다. (이 부분 때문에 맞는 정답이 계속 틀려서 원인을 한참동안 찾았습니다..)

다음은 코드입니다.

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

public class Main{

    static int N,M,K;
    static int res = 0;
    static int[] dx = {-1,0,1,1,1,0,-1,-1};
    static int[] dy = {-1,-1,-1,0,1,1,1,0};
    static int[][] addFood = new int[11][11];
    static int[][] farm = new int[11][11];
    // 나무 나이 정렬을 위해서 Priority Queue 사용
    static PriorityQueue<Tree> trees =  new PriorityQueue<>();
    static PriorityQueue<Tree> deadTrees =  new PriorityQueue<>();

    // 봄
    // 나무가 자신의 나이만큼 양분을 먹고 나이가 1 증가
    static void spring(){
        // 큐에서 poll할 시 데이터가 큐에서 빠지므로 빠진 데이터를 모아놓을 리스트 할당
        PriorityQueue<Tree> list = new PriorityQueue<>();

        while(!trees.isEmpty()){
            Tree tree = trees.poll();
            int y = tree.y;
            int x = tree.x;
            int age = tree.age;

            // 땅에 자신이 먹을 수 있는 양분이 있다면 자신의 나이만큼 양분 먹음
            if(farm[y][x] >= age){
                farm[y][x] -= age;
                // 나무가 살아있으므로 나이 1 증가시켜서 임시 리스트에 추가
                list.add(new Tree(x,y,age+1));
            }
            // 만약 땅에 양분이 부족하다면 나무는 죽음
            else deadTrees.add(tree);
        }

        // 임시 리스트에 저장된 데이터 trees에 저장
        trees = new PriorityQueue<>(list);
    }

    // 여름
    // 봄에 죽은 나무가 양분으로 변함
    static void summer(){
        while(!deadTrees.isEmpty()){
            Tree deadTree = deadTrees.poll();
            // 죽은 나무의 나이를 2로 나눈 값(소수점 생략)이 양분으로 추가
            int food = deadTree.age/2;
            int y = deadTree.y;
            int x = deadTree.x;
            farm[y][x] += food;
        }
    }

    // 가을
    // 나무 번식
    static void fall(){
        // 큐에서 poll할 시 데이터가 큐에서 빠지므로 빠진 데이터를 모아놓을 리스트 할당
        PriorityQueue<Tree> list = new PriorityQueue<>();

        while(!trees.isEmpty()){
            Tree tree = trees.poll();
            int y = tree.y;
            int x = tree.x;
            int age = tree.age;

            // 나이가 5의 배수인 나무가 번식
            if(age%5 == 0){
                // 인접한 8개의 칸에 나이가 1인 나무 생성
                for(int dir=0;dir<8;dir++){
                    int ny = y + dy[dir];
                    int nx = x + dx[dir];
                    if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
                    // 임시 리스트에 나무 데이터 추가
                    list.add(new Tree(nx,ny,1));
                }
            }
            // 임시 리스트에 나무 데이터 추가
            list.add(tree);
        }

        // 임시 리스트에 저장된 데이터 trees에 저장
        trees = new PriorityQueue<>(list);
    }

    // 겨울
    // 양분 추가
    static void winter(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                farm[i][j] += addFood[i][j];
            }
        }
    }

    static void doInvestment(int year){
        if(year == K){
            res = trees.size();
            return;
        }

        spring();
        summer();
        fall();
        winter();

        doInvestment(year+1);
    }

    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());

        // 각 칸에 추가될 양분 데이터
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                addFood[i][j] = Integer.parseInt(st.nextToken());
                // 처음 양분의 양 : 5
                farm[i][j] = 5;
            }
        }

        // 나무 데이터
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            // 1부터 시작하므로 좌표값 -1씩 진행
            trees.add(new Tree(x-1,y-1,z));
        }

        // K년이 지난 후 살아있는 나무의 개수이므로 0부터 시작
        doInvestment(0);
        System.out.println(res);
    }
}

// 나이가 적은 순으로 양분을 먹으므로 나이 순 오름차순으로 데이터 추가 필요
class Tree implements Comparable{
    int x;
    int y;
    int age;

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

    @Override
    public int compareTo(Object o) {
        Tree tree = (Tree) o;
        if(tree.age < age) return 1;
        else if(tree.age > age) return -1;
        else return 0;
    }
}