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

문제 링크

16235번: 나무 재테크

 

 

풀이 )

  하나의 칸에 여러 나무가 있을 때 나이가 적은 나무부터 양분을 공급한다는 내용을 보고 우선순위큐를 사용했다.

  feed 배열에는 양분을 저장했고, a 배열에는 겨울마다 늘어나는 양분을 저장했다.

  

  나무의 좌표와 나이를 저장하는 우선순위큐를 만들어서 나이가 낮은 순으로 poll 되도록 구현했다.

  처음에는 우선순위큐 하나만 사용해서 구현하려고했기 때문에 큐의 크기를 먼저 구한 후 큐의 크기만큼만 반복문을 돌렸지만, 이런 경우 중간에 나이가 낮은 나무가 들어오는 경우 의도와 다르게 나오는 경우가 있었기 때문에 다른 우선순위 큐를 선언해서 사용했다.

 

  나머지는 문제에서 요구하는 순서대로 구현했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
    static int[] dy = {1, 1, 0, -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[][] feed = new int[n+1][n+1];
        int[][] a = new int[n+1][n+1];

        PriorityQueue<Info> treeQ = new PriorityQueue<>((o1, o2)->{
            return o1.age-o2.age;
        });
        Queue<Info> dieQ = new LinkedList<>();

        for(int i = 1; i <= n; ++i){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1; j <= n; ++j){
                feed[i][j] = 5;
                a[i][j] = 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());
            treeQ.offer(new Info(x, y, age));
        }
        // 입력

        while(k-- > 0) {
            PriorityQueue<Info> tmp = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            int size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                int x = tree.x, y = tree.y, age = tree.age;
                if (feed[x][y] >= age) {
                    feed[x][y] -= age;
                    age++;
                    tmp.offer(new Info(x, y, age));
                } else
                    dieQ.offer(new Info(x, y, age));
            }
            treeQ = tmp;
            // 봄

            while (!dieQ.isEmpty()) {
                Info die = dieQ.poll();
                feed[die.x][die.y] += die.age / 2;
            }
            // 여름

            PriorityQueue<Info> tmp2 = new PriorityQueue<>((o1, o2)->{
                return o1.age-o2.age;
            });
            size = treeQ.size();
            while (size-- > 0) {
                Info tree = treeQ.poll();
                tmp2.offer(tree);
                if (tree.age % 5 == 0) {
                    int x = tree.x, y = tree.y;
                    for (int dir = 0; dir < 8; ++dir) {
                        int nx = x + dx[dir], ny = y + dy[dir];
                        if (0 < nx && nx <= n && 0 < ny && ny <= n)
                            tmp2.offer(new Info(nx, ny, 1));
                    }
                }
            }
            treeQ = tmp2;
            // 가을

            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= n; ++j)
                    feed[i][j] += a[i][j];
            }
            // 겨울
        }
        System.out.println(treeQ.size());
    }

    static class Info{
        int x, y, age;

        public Info(int x, int y, int age) {
            this.x = x;
            this.y = y;
            this.age = age;
        }
    }
}