[백준] 나무 제테크 - 16235번

문제설명

www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

기본아이디어

구현할 내용이 꽤 많다. 하지만 각각의 기능을 보면 간단하다. 

 

봄 : 양분이 자신의 나이보다 많이 남아있으면 나이가 한살 많아지고, 양분이 적으면 바로 죽는다.여름 : 죽은 나무들의 나이 / 2 를 양분에 추가한다.가을 : 나이 % 5 == 0 인 나무들이 자신을 기준으로 주위 8칸에 나이 1인 나무를 추가한다.겨울 : 각 위치에 양분을 정해진 만큼 추가한다.

 

자료구조는 나무들이 나이순으로 나오는 PriorityQueue를 하나 사용하고, 나무가 죽으면 들어갈 Queue 하나랑 살아남으면 들어갈 Queue 하나를 사용했다.

 

구현코드

public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(input.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
 
        A = new int[N][N];
        for (int i = 0; i < N; i++){
            st = new StringTokenizer(input.readLine());
            int[] temp = new int[N];
            for(int j = 0; j < N; j++)
                temp[j] = Integer.parseInt(st.nextToken());
            A[i] = temp;
        }
        B = new int[N][N];
        for (int i = 0; i < N; i++){
            for(int j = 0; j < N; j++)
                B[i][j] = 5;
        }
 
        pq = new PriorityQueue<>(new QComparator());
        dead = new LinkedList<>();
        alive = new LinkedList<>();
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(input.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int age = Integer.parseInt(st.nextToken());
            pq.add(new int[]{x,y,age, 0});
        }
        for(int i = 0; i < K; i++){
            spring();
            summer();
            autumn();
            winter();
        }
        System.out.println(pq.size());
    }
 
    static class QComparator implements Comparator<int[]>{
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[2] - o2[2];
        }
    }
    static int N, M, K;
    static int[][] A;
    static int[][] B;
    static PriorityQueue<int[]> pq;
    static Queue<int[]>dead;
    static Queue<int[]>alive;
    static void spring(){
        int size = pq.size();
        for(int i = 0; i < size; i++){
            int[] loc = pq.poll();
            if(B[loc[0]][loc[1]] >= loc[2]){
                B[loc[0]][loc[1]] -= loc[2];
                alive.add(new int[]{loc[0],loc[1],loc[2]+1});
            }else{
                dead.add(loc);
            }
        }
    }
    static void summer(){
        while(!dead.isEmpty()){
            int[] loc = dead.poll();
            B[loc[0]][loc[1]] += loc[2]/2;
        }
    }
    static int[] dr = {0, 0, 1, 1, 1, -1, -1, -1};
    static int[] dc = {-1, 1, -1, 0, 1, -1, 0, 1};
    static void autumn(){
        while(!alive.isEmpty()){
            int[] loc = alive.poll();
            if(loc[2] % 5 == 0) {
                for (int d = 0; d < 8; d++) {
                    int nr = loc[0] + dr[d];
                    int nc = loc[1] + dc[d];
                    if (isIn(nr, nc)) {
                        pq.add(new int[]{nr, nc, 1});
                    }
                }
            }
            pq.add(loc);
        }
    }
    static boolean isIn(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < N;
    }
    static void winter(){
        for (int i = 0; i < N; i++){
            for(int j = 0; j < N; j++)
                B[i][j] += A[i][j];
        }
    }
 
 

 

정리, 기억할 내용

1. 구현할게 많은 문제라면 코딩전에 확실히 구조를 정해놓고 하자.

2. 필요한 자료구조 생각하자.