[Algorithm] SW 기출문제 - 나무 재테크(16235) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 - 나무 재테크 자바 풀이를 작성하고자 합니다.

제가 제일 좋아하는 우선순위 큐 스케줄링 유형으로 정말 재밌게 풀었던 것 같습니다.

 

문제 출처: https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        
        TreeInvestment treeInvestment = new TreeInvestment(n, k);
        
        for (int row = 1; row <= n; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= n; col++)
                treeInvestment.setNutrientMap(row, col, parseInt(st.nextToken())); // 영양분 초기화
        }
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            treeInvestment.setTrees(parseInt(st.nextToken()), parseInt(st.nextToken()), parseInt(st.nextToken())); // 트리 추가
        }
        
        treeInvestment.start();
        System.out.println(treeInvestment.getAlive());
    }    
}

class TreeInvestment {
    
    static final int[] DR = {-1, -1, -1, 0, 0, 1, 1, 1}; // 8개 방향 설정
    static final int[] DC = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    int n; // n + 1 by n + 1 행렬
    int k; // k년 후
    int[][][] nutrientMap; // 영양분 맵
    PriorityQueue<Tree> springQueue = new PriorityQueue<>(Comparator.comparing((Tree tr) -> tr.age)); // 봄에 살아 있는 나무  우선순위 큐
    Queue<Tree> autumnQueue = new ArrayDeque<>(); // 가을에 살아 있는 나무 큐
    Queue<Tree> summerQueue = new ArrayDeque<>(); // 여름 큐 (죽은 나무 영양분을 위해)
    
    TreeInvestment(int n, int k) {
        this.n = n;
        this.k = k;
        
        nutrientMap = new int[2][n + 1][n + 1]; // 3차원 배열의 1차원 --> 0: 현재, 1: 매년 추가되는 양분의 양
       
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                nutrientMap[0][row][col] = 5;  // 5 초기화
            }
        }
    }
    
    void setNutrientMap(int row, int col, int value) {
        nutrientMap[1][row][col] = value; // 매년 추가되는 양분의 양 초기화
    }
    
    void setTrees(int row, int col, int age) {
        springQueue.add(new Tree(row, col, age)); // 트리 스프링큐에 추가하기 
    }
    
    void start() {
        int nowK = 0; // 0년 째
        
        while (nowK < k) {
            while(!springQueue.isEmpty()) { // 봄          
                Tree tree = springQueue.poll();
                int row = tree.row;
                int col = tree.col;

                if (nutrientMap[0][row][col] >= tree.age) {
                    nutrientMap[0][row][col] -= tree.age; // 나이만큼 양분 제거
                    tree.age++; // 나이 ++
                    autumnQueue.add(tree); // 다음 큐에 추가 (내년에도 살아 있게 됨)
                } 
                
                else summerQueue.add(tree); // 여름에 양분 추가를 위해 여름큐 등록
            }
            
            while (!summerQueue.isEmpty()) { // 여름 양분 등록하기 
                Tree tree = summerQueue.poll();
                nutrientMap[0][tree.row][tree.col] += tree.age / 2; // 죽은 나무는 나이 / 2의 양만큼 영양분
            }
            
            while(!autumnQueue.isEmpty()) { // 가을
                Tree tree = autumnQueue.poll();
                
                if (tree.age % 5 == 0) { // 5의 배수는 번식
                    
                    for (int k = 0; k < 8; k++) {
                        int nextR = tree.row + DR[k];
                        int nextC = tree.col + DC[k];
                        
                        if (!isValid(nextR, nextC)) continue;
                        springQueue.add(new Tree(nextR, nextC, 1)); // 나무가 생긴 것은 springQueue에 등록
                    }
                }
                springQueue.add(tree); // 번식한 트리도 queue에 추가
            }
            
            for (int row = 1; row <= n; row++) { // 겨울은 양분을 추가함
                for (int col = 1; col <= n; col++) 
                    nutrientMap[0][row][col] += nutrientMap[1][row][col];
            }
            
            nowK++; // 1년이 지남
        }
        
    }
    
    int getAlive() { // k년뒤에도 살아있다는 것은 springQueue에 있다는 것을 의미
        return springQueue.size();
    }
    
    boolean isValid (int row, int col) {
        return row > 0 && row <= n && col > 0 && col <= n; // 1, 1 시작이므로
    }
    
    static class Tree {
        int row;
        int col;
        int age;
        
        Tree (int row, int col, int age) {
            this.row = row;
            this.col = col;
            this.age = age;
        }
    }
}

 

 

2. 풀이 중점 사항

 

이번 문제는 봄, 여름, 가을, 겨울 각 상황에 따라 나무가 죽거나 살고, 영양분이 추가되는 일련의 과정을 하나의 스케줄링으로 처리하는 과정이 필요했습니다.

 

int n; // n + 1 by n + 1 행렬
int k; // k년 후
int[][][] nutrientMap; // 영양분 맵
PriorityQueue<Tree> springQueue = new PriorityQueue<>(Comparator.comparing((Tree tr) -> tr.age)); // 봄에 살아 있는 나무  우선순위 큐
Queue<Tree> autumnQueue = new ArrayDeque<>(); // 가을에 살아 있는 나무  우선순위 큐
Queue<Tree> summerQueue = new ArrayDeque<>(); // 여름 큐 (죽은 나무 영양분을 위해)

 

양분은 현재 있는 양분과 겨울에 추가되는 양분을 구분하기 위해 3차원 배열로 선언하여 1차원의 0번째 인덱스는 현재 양분의 양,

1번 인덱스는 겨울에 추가되는 양분의 양을 기록하였습니다.

 

봄, 여름, 가을에 대해 각각 우선순위 큐, 큐, 큐를 적용하여 봄에 살아 있는 나무, 죽어서 여름에 양분이 되는 나무, 가을에 살아서 번식하는 나무를 큐에 추가할 수 있도록 설정하였습니다.

 

나무의 나이가 적은 순서대로 먼저 양분을 획득하도록 해야 하므로 봄은 우선순위 큐로 적용하였습니다. 

 

    while(!springQueue.isEmpty()) { // 봄          
        Tree tree = springQueue.poll();
        int row = tree.row;
        int col = tree.col;

        if (nutrientMap[0][row][col] >= tree.age) {
            nutrientMap[0][row][col] -= tree.age; // 나이만큼 양분 제거
            tree.age++; // 나이 ++
            autumnQueue.add(tree); // 다음 큐에 추가 (내년에도 살아 있게 됨)
        } 

        else summerQueue.add(tree); // 여름에 양분 추가를 위해 여름큐 등록
    }

    while (!summerQueue.isEmpty()) { // 여름 양분 등록하기 
        Tree tree = summerQueue.poll();
        nutrientMap[0][tree.row][tree.col] += tree.age / 2; // 죽은 나무는 나이 / 2의 양만큼 영양분
    }

 

중점사항은, 죽은 나무는 springQueue에 있는 모든 나무가 처리된 이후 양분으로 추가해야 합니다. 왜냐하면, 봄 -> 여름이라는 스케줄이 있기 때문에 죽었다고 해서 바로 양분으로 처리하면, 답이 다르게 처리될 수 있습니다.

 

while(!autumnQueue.isEmpty()) { // 가을
    Tree tree = autumnQueue.poll();

    if (tree.age % 5 == 0) { // 5의 배수는 번식

        for (int k = 0; k < 8; k++) {
            int nextR = tree.row + DR[k];
            int nextC = tree.col + DC[k];

            if (!isValid(nextR, nextC)) continue;
            springQueue.add(new Tree(nextR, nextC, 1)); // 나무가 생긴 것은 springQueue에 등록
        }
    }
    springQueue.add(tree); // 번식한 트리도 queue에 추가
}

for (int row = 1; row <= n; row++) { // 겨울은 양분을 추가함
    for (int col = 1; col <= n; col++) 
        nutrientMap[0][row][col] += nutrientMap[1][row][col];
}

nowK++; // 1년이 지남

 

가을에서 번식에 성공을 마치고 나면 봄 우선순위 큐에 다시 추가하여, 봄에도 살아있을 수  있도록 처리하였습니다.

겨울은 양분을 추가하였고 겨울까지 마친 후 nowK++로 1년이 지나도록 설정하였습니다.

 

이상으로 나무 재테크 자바 풀이를 마치도록 하겠습니다.

감사합니다.!!!