[시뮬레이션] 나무 재태크

백준 16235번 나무 재태크 (삼성전자 SW 역량테스트 기출)

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

package 나무재태크;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int N; //맵크기
    static int M; //나무수
    static int K; //년

    static Ground[][] map;

    static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -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());

        map = new Ground[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] = new Ground( Integer.parseInt(st.nextToken()) );
            }
        }


        //나무심기
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());

            map[x][y].addTree(age);
        }

        //세월아 흘러라
        for(int year=0; year<K; year++){

            //봄&여름
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){
                    PriorityQueue<Integer> buffer = new PriorityQueue<>();

                    
                    int dieFood = 0; //죽어서 생긴 양분
                    
//해당 땅의 나무들 검사
                    while (!map[i][j].getTrees().isEmpty()){
                        int nowTree = map[i][j].trees.poll();

                        if(nowTree<=map[i][j].food){
                            map[i][j].food -= nowTree;
                            buffer.add(nowTree+1);
                        }else{
                            dieFood += nowTree/2;
                        }
                    }

                    //정산
                    map[i][j].trees = buffer;   //살아남은 나무들
                    map[i][j].food += dieFood;  //죽어서 양분이 된 나무들
                }
            }


            //가을(번식) & 겨울(양분추가)
            for(int i=1; i<=N; i++){
                for(int j=1; j<=N; j++){

                    for(int tree: map[i][j].getTrees()){
                        if(tree%5==0) breeding(i,j);
                    }

                    map[i][j].addFood();
                }
            }


        }

        //나무의 수 출력
        int treeCount=0;
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                treeCount += map[i][j].getTreeCount();
            }
        }
        System.out.println(treeCount);

    }


    //입력받은 칸 주위 8칸으로 번식
    static void breeding(int a, int b){

        for(int i=0; i<8; i++){

            int x = a + dx[i];
            int y = b + dy[i];

            //범위내부
            if(1<= x && x<=N && 1<= y && y <= N){
                map[x][y].addTree(1);
            }
        }
    }



    static class Ground{

        private PriorityQueue<Integer> trees;
        private int food;
        private int yearFood; //매년 추가되는 양분


        public Ground(int yearFood){
            trees = new PriorityQueue<>();
            this.food = 5;
            this.yearFood = yearFood;
        }


        void addTree(int treeAge){
           this.trees.add(treeAge);
        }

        PriorityQueue<Integer> getTrees(){
            return trees;
        }

        //이 땅의 나무가 몇개인지 반환
        int getTreeCount(){
            return trees.size();
        }

        //매년 할당된 양의 양분을 추가
        void addFood(){
            this.food += this.yearFood;
        }
    }
}

이건 손으로 따라가며 디버깅하는게 거의 불가능.

차근차근 풀고 안되면 다시 짜는게 좋을듯.

틀렸던 부분

되는거

static void eat2(Ground g){

    if(g.trees.isEmpty()) return;
    PriorityQueue<Integer> buffer = new PriorityQueue<>();
    int dieFood = 0; //죽어서 생긴 양분

    while (!g.trees.isEmpty()){
        int nowTree = g.trees.poll();

        if(nowTree<=g.food){
            g.food -= nowTree;
            buffer.add(nowTree+1);
        }else{
            dieFood += nowTree/2;
            treeCount--;
        }
    }

    //정산
    g.trees = buffer;   //살아남은 나무들
    g.food += dieFood;  //죽어서 양분이 된 나무들
}

안되는거

static void eat1(Ground g){

    if(g.trees.isEmpty()) return;
    PriorityQueue<Integer> buffer = new PriorityQueue<>();
    int dieFood = 0; //죽어서 생긴 양분

    for(int tree: g.trees){

        System.out.printf("%d ",tree);

        if(tree <= g.food){
            g.food -= tree;
            buffer.add(tree+1);
        }else{
            treeCount--;
            dieFood += (tree/2); //양분으로.
        }
    }
    System.out.println();

    g.trees = buffer;
    g.food += dieFood;
}

다시 풀어봤는데 안되서 이전 소스와 비교.

eat1은 안되고 eat2는 된다.

for(int tree: g.trees){
    ...
}

이렇게 한다고 해서 tree안의 내용물은 순서대로 나오지 않는다.

앞에서부터 poll해줘야만 순서대로 나옴.

테스트케이스

10 1 1000

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

100 100 100 100 100 100 100 100 100 100

1 1 1

5449