문제링크

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

구현방법

• 크기는 N X N

  모든 칸은 양분이 5가 기본으로 있음.

  나무가 자신의 나이만큼 양분을 먹는다 -> 먹으면 나이가 1 증가

  한 땅에 여러개의 나무가 심어져있을 수 있음.

  • 여러개일 경우 나무의 나이가 어린순으로 양분을 먼저 먹는다.

    • 대신 양분이 부족해서 자신의 나이만큼 못먹는 나무는 즉시 죽음.
    • 죽은 나무는 양분으로 변한다.
      • 양분은 죽은 나무의 나이 /2 만큼 그 칸에 양분 추가.
      • 소수점은 버림.

    사계절이 존재함.

  • 봄 : 나이만큼 양분을 먹는다.먹으면 나이+1 못먹는 나무는 죽음.

  • 여름 : 봄에 죽은 나무들이 양분으로 변함(여기서 계산해서 칸에 양분 추가.)

  • 가을 : 나무가 번식한다. 나무의 나이가 5의배수이면 가능하다. 인접 8칸에 나이가 1인 나무가 생김.

  • 겨울 : 기계가 각 땅에 양분을 추가. -> 각 땅의 양분만큼 추가된다.

    K년이 지난후 -> 0년부터 K까지 반복문돌면됨.

    결과는 살아있는 나무의 개수

    살아있는 나무와 죽은 나무를 분리해서 계산해야함.

  • 죽은 나무는 여름에 양분이 되야하고

  • 살아있는 나무는 봄에 나이를 먹어야하기 때문에.

    사계절 코드를 그대로 구현하면된다.

    처음에 나무가 나이순으로 정렬되있지 않기 때문에 처음 나무 입력을 받은 것을 나이순으로 정렬하고 진행

  • 그후 새로 생기는 나무들은 deque의 addFirst를 통해서 맨앞에 넣어줌으로써 나이순이 계속 유지되게 해준다.

알고리즘

• 구현,시뮬레이션

CODE

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

public class Main {

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

    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());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] map = new int[N+1][N+1];
        int[][] eat = new int[N+1][N+1];


        Deque<Tree> tree_list = new ArrayDeque<>();


        List<Tree> list = new ArrayList<>();
        //기본 입력으로 주어지는거 넣어주기.
        for(int row = 1; row <=N;row++){
            st= new StringTokenizer(br.readLine());
            for(int col=1;col<=N;col++){
                map[row][col] = Integer.parseInt(st.nextToken());
                eat[row][col] = 5;
            }
        }

        for(int idx =1 ;idx <=M;idx++){
            st = new StringTokenizer(br.readLine());

            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());

            int age = Integer.parseInt(st.nextToken());
            list.add(new Tree(row,col,age));
        }

        //처음 나무 나이순 정렬
        Collections.sort(list);
        for(Tree t : list){
            tree_list.offer(t);
        }

        while(K-->0){
            Queue<Tree> tree_die = new LinkedList<>();

            //봄
            for(int idx = 0; idx <tree_list.size();){
                Tree cur = tree_list.poll();
                if(eat[cur.row][cur.col] >= cur.age){
                    eat[cur.row][cur.col] -= cur.age;
                    cur.age+=1;
                    idx++;
                    tree_list.add(cur);
                }else{
                    tree_die.offer(cur);
                }
            }


            //여름
            for(Tree tree : tree_die){
                eat[tree.row][tree.col] += tree.age/2;
            }


            //가을
            Queue<Tree> temp = new LinkedList<>();
            //5의배수를 만족하면 넣어놓음.
            for(Tree tree : tree_list){
                if(tree.age % 5 == 0){
                    temp.offer(tree);
                }
            }
            while(!temp.isEmpty()){
                Tree t = temp.poll();

                for(int idx= 0 ; idx <8;idx++){
                    int nxt_row = t.row + dx[idx];
                    int nxt_col = t.col + dy[idx];

                    if(nxt_row > 0 && nxt_row <= N && nxt_col >0 && nxt_col <= N){
                        tree_list.addFirst(new Tree(nxt_row,nxt_col,1));
                    }
                }
            }

            //겨울
            for(int row =1 ;row <=N;row++){
                for(int col=1 ;col<=N;col++){
                    eat[row][col] += map[row][col];
                }
            }
        }

        System.out.println(tree_list.size());

        br.close();
    }



    public static class Tree implements Comparable<Tree>{
        int row;
        int col;
        int age;

        public Tree(int row, int col, int age) {
            this.row = row;
            this.col = col;
            this.age = age;
        }

        @Override
        public int compareTo(Tree o) {
            return this.age - o.age;
        }
    }
}

실패 코드

우선순위 큐로 하는 경우

• 지속적으로 정렬이 진행되기 때문에 시간이 많이 소요되서 시간초과 발생

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

public class Main {

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

    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());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] map = new int[N+1][N+1];
        int[][] eat = new int[N+1][N+1];


        Queue<Tree> tree_list = new PriorityQueue<>();
        //기본 입력으로 주어지는거 넣어주기.
        for(int row = 1; row <=N;row++){
            st= new StringTokenizer(br.readLine());
            for(int col=1;col<=N;col++){
                map[row][col] = Integer.parseInt(st.nextToken());
                eat[row][col] = 5;
            }
        }

        for(int idx =1 ;idx <=M;idx++){
            st = new StringTokenizer(br.readLine());

            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());

            int age = Integer.parseInt(st.nextToken());
            tree_list.offer(new Tree(row,col,age));
        }

        while(K-->0){
            Queue<Tree> tree_die = new LinkedList<>();
            
            //봄
            for(int idx = 0; idx <tree_list.size();){
                Tree cur = tree_list.poll();
                if(eat[cur.row][cur.col] >= cur.age){
                    eat[cur.row][cur.col] -= cur.age;
                    cur.age+=1;
                    idx++;
                    tree_list.add(cur);
                }else{
                    tree_die.offer(cur);
                }
            }
            
            
            //여름
            for(Tree tree : tree_die){
                eat[tree.row][tree.col] += tree.age/2;
            }
            
            
            //가을
            Queue<Tree> temp = new LinkedList<>();
            //5의배수를 만족하면 넣어놓음.
            for(Tree tree : tree_list){
                if(tree.age % 5 == 0){
                    temp.offer(tree);
                }
            }
            while(!temp.isEmpty()){
                Tree t = temp.poll();

                for(int idx= 0 ; idx <8;idx++){
                    int nxt_row = t.row + dx[idx];
                    int nxt_col = t.col + dy[idx];

                    if(nxt_row > 0 && nxt_row <= N && nxt_col >0 && nxt_col <= N){
                        tree_list.offer(new Tree(nxt_row,nxt_col,1));
                    }
                }
            }
            
            //겨울
            for(int row =1 ;row <=N;row++){
                for(int col=1 ;col<=N;col++){
                    eat[row][col] += map[row][col];
                }
            }
        }

        System.out.println(tree_list.size());

        br.close();
    }



    public static class Tree implements Comparable<Tree>{
        int row;
        int col;
        int age;

        public Tree(int row, int col, int age) {
            this.row = row;
            this.col = col;
            this.age = age;
        }

        @Override
        public int compareTo(Tree o) {
            return this.age - o.age;
        }
    }
}