[BJ]G4 16235 나무 재테크

BJ G4 16235 나무 재테크

 

 

문제링크

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

16235번: 나무 재테크

 

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

BJ G4 16235 나무재테크 - YouTube

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @author 은서파
 * @since 2021/12/02
 * @see https://www.acmicpc.net/problem/16235
 * @performance 24324 192
 * @category #시뮬레이션
 */

public class BJ_G4_16235_나무재테크 {

    private static int N, M, K;
    private static TreeMng[][] map;
    private static int[][] deltas = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 } };

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));
        StringTokenizer tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken()) + 1; // 지도의 r, c는 1부터 시작한다.
        M = Integer.parseInt(tokens.nextToken());
        K = Integer.parseInt(tokens.nextToken());

        map = new TreeMng[N][N];
        for (int r = 1; r < N; r++) {
            tokens = new StringTokenizer(input.readLine());
            for (int c = 1; c < N; c++) {
                map[r][c] = new TreeMng(r, c, Integer.parseInt(tokens.nextToken()));
            }
        }

        // 나무 정보 - 입력으로 들어오는 나무들의 위치는 모두 다르다!
        for (int m = 0; m < M; m++) {
            tokens = new StringTokenizer(input.readLine());
            int r = Integer.parseInt(tokens.nextToken());
            int c = Integer.parseInt(tokens.nextToken());
            int a = Integer.parseInt(tokens.nextToken());
            // a 살짜리 나무 하나 심어주기.
            map[r][c].addTree(a, 1);
        }// 입력 완료!!

        for (int k = 0; k < K; k++) {
            for (int r = 1; r < N; r++) {
                for (int c = 1; c < N; c++) {
                    map[r][c].spring();
                    map[r][c].summer();
                }
            }

            // 가을의 동작은 다른 cell에도 영향을 주므로 봄과 따로 처리 필요
            for (int r = 1; r < N; r++) {
                for (int c = 1; c < N; c++) {
                    map[r][c].fall();
                    map[r][c].winter();
                }
            }
        }
        System.out.println(M);
    }

    static class Tree {
        int age, cnt;

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

    }

    static class TreeMng {
        int r, c;
        int n; // 현재 cell에 있는 양분
        int dn; // 겨울에 추가될 양분 - 입력값
        int refill;// 봄에 죽은 나무들이 양분으로 되기 전에 잠시 머물러 있는 곳
        List<Tree> trees;

        public TreeMng(int r, int c, int dn) {
            this.r = r;
            this.c = c;
            this.dn = dn;
            this.n = 5;// 초기 양분은 5
            this.trees = new LinkedList<>(); // 앞으로 뒤로 데이터가 추가/삭제 되어야 하니까.
        }

        /**
         * 몇살짜리 나무를 몇 개 추가할 것인가?
         * 1살짜리라면 맨 앞에, 아니면 맨 뒤에
         * 
         * @param age
         * @param cnt
         */
        public void addTree(int age, int cnt) {
            if (trees.size() == 0 || age > 1) {
                trees.add(new Tree(age, cnt));
            } else {
                // 만약에 기존에 1살짜리가 있었다면?
                if (trees.get(0).age == 1) {
                    trees.get(0).cnt += cnt;
                }
                // 막내동생 추가요!!!
                else {
                    trees.add(0, new Tree(age, cnt));
                }
            }
        }

        public void spring() {
            int size = trees.size();
            if (size == 0) {
                return;
            }
            // 현재 trees에 있는 녀석들만을 대상으로 한다(새롭게 추가되는 녀석들은 제외)
            for (int i = 0; i < size; i++) {
                // 저장된 순서가 바로 나이순!!
                Tree tree = trees.remove(0);
                // 나이, 개수 --> 현재의 양분으로 몇 그루의 나무를 먹일 수 있을까?
                int cnt = Math.min(n / tree.age, tree.cnt);

                // cnt 이내는 양분을 먹고 나이 증가
                if (cnt > 0) {
                    n -= cnt * tree.age;
                    addTree(tree.age + 1, cnt);
                }
                // 나머지가 있다면? 사망 - 나이/2만큼 여름에 양분으로 변신!
                refill += (tree.age / 2) * (tree.cnt - cnt);
                // 사망 처리
                M -= tree.cnt - cnt;
            }
        }

        public void summer() {
            n += refill;
            refill = 0;
        }

        public void fall() {
            for (Tree tree : trees) {
                // 나이가 5의 배수이면 8방향에 나이 1인 나무 추가하기
                if (tree.age % 5 == 0) {
                    for (int d = 0; d < deltas.length; d++) {
                        int nr = r + deltas[d][0];
                        int nc = c + deltas[d][1];
                        if (isIn(nr, nc)) {
                            map[nr][nc].addTree(1, tree.cnt);
                            M += tree.cnt;
                        }
                    }
                }
            }
        }

        public void winter() {
            n += dn;
        }

        // r과 c는 1부터 시작!!
        private boolean isIn(int r, int c) {
            return 1 <= r && r < N && 1 <= c && c < N;
        }
    }

    // REMOVE_START
    static String src = "5 2 6\n" +
                        "2 3 2 3 2\n" +
                        "2 3 2 3 2\n" +
                        "2 3 2 3 2\n" +
                        "2 3 2 3 2\n" +
                        "2 3 2 3 2\n" +
                        "2 1 3\n" +
                        "3 2 3";
    // REMOVE_END
}