Java 16235 나무 재테크

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

16235번: 나무 재테크

---

문제를 보고 처음 시도한 접근은 양분, 나무들의 나이를 기준으로 정렬된 우선순위 큐가 필드값으로 있는 map이란 클래스와 map을 저장할 2차원 배열을 만든 뒤 나무가 있는 좌표가 저장된 set을 만들어 해당 문제를 풀어보았습니다.

클래스 객체를 set에 저장하기 위해서 클래스에서 좌표값을 기준으로 hashcode함수와 equals 함수를 재정의하여 구현하였으나 시간초과가 났고 잘못된 방법으로 접근하고 있는 거 같아서 다시 풀었습니다.

---

 

풀이 :

살아있는 나무들을 저장할 덱, 번식 조건에 맞는 나무들을 저장할 리스트, 죽은 나무들을 저장할 큐 세가지로 해당 문제를 구현할 수 있었습니다.

먼저 문제에서 주어진 입력값을 차례대로 받은 뒤 while문을 통해서 봄 여름 가을 겨울 순으로 해당 로직들을 구현하였습니다.

 

봄 : 살아있는 나무가 있는 덱을 앞에서부터 뽑은 뒤 양분을 흡수할 수 있다면 흡수하고 나이가 5로 나눈 나머지가 0일 경우엔 번식 리스트에 넣어주고 다시 덱에 추가해줍니다. 아닐 경우에는 죽은 나무가 들어갈 큐에 저장해준뒤 봄의 로직은 끝입니다.

 

여름 : 죽은 나무가 들어간 큐에 모든 원소를 뽑아서 해당 좌표에 나이/2 를 한 값을 더해줍니다.

 

가을 : 번식 조건에 맞는 리스트의 모든 원소를 순회하며 인접한 칸에 새로운 나무를 심어주고 덱의 첫번째자리에 추가해줍니다.(나이가 어린 나무들이 먼저 양분을 흡수해야하기 때문에)

 

겨울 : 입력받아둔 공급할 양분의 2차원 배열을 map에 더해줍니다.

 

위의 차례로 해당 문제를 풀 수 있었습니다.

---

 

 

 

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

public class Main {
    static int n,m,k;
    static int[][] map;
    static int[][] supply;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    static Deque<Tree> aliveTrees;
    static ArrayList<Tree> spread;
    static Queue<Tree> deadTrees;
    static class Tree {
        int x;
        int y;
        int age;

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

    public static void main(String[] args)throws IOException {
        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 int[n+1][n+1];
        supply = new int[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] = 5;
                supply[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        aliveTrees = new ArrayDeque<>();
        deadTrees = new LinkedList<>();
        spread = new ArrayList<>();

        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());
            aliveTrees.addFirst(new Tree(x,y,age));
        }

        while(k --> 0){
            //봄
            Deque<Tree> tmp = new ArrayDeque<>();
            ArrayList<Tree> spread = new ArrayList<>();
            while(!aliveTrees.isEmpty()){
                Tree tree = aliveTrees.pollFirst();
                if(map[tree.x][tree.y] >= tree.age){
                    map[tree.x][tree.y] -= tree.age;
                    tree.age++;
                    tmp.addLast(tree);
                    if(tree.age % 5 == 0){
                        spread.add(tree);
                    }
                }else {
                    deadTrees.offer(tree);
                }
            }
            while(!tmp.isEmpty()){
                aliveTrees.addLast(tmp.pollFirst());
            }

            //여름
            while(!deadTrees.isEmpty()){
                Tree tree = deadTrees.poll();
                map[tree.x][tree.y] += tree.age/2;
            }

            //가을
            for(int i = 0; i < spread.size(); i++){
                Tree tree = spread.get(i);
                for(int j = 0; j < 8; j++){
                    int nx = tree.x + dx[j];
                    int ny = tree.y + dy[j];

                    if(nx < 1 || ny < 1 || nx > n || ny > n){
                        continue;
                    }
                    aliveTrees.addFirst(new Tree(nx,ny,1));
                }
            }

            //겨울
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    map[i][j] += supply[i][j];
                }
            }
        }

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

    }
}