16235. 나무 재테크

INFO

링크: 문제 보러가기

언어: Java

난이도: 3

알고리즘: 구현 시뮬레이션

소요 시간:

1. 문제 이해

핵심 요구사항

땅: NxN
양분 per 땅
- 초기 값: 5
나무 per 땅
- 각 땅에 나무 여러 그루가 있을 수 있음
계절:
- 봄: 나무 성장
  - 양분 -= each 나무 나이
  - each 나무 나이 += (양분 有) 1 : (양분 無) 사망
  - 어린 나무 부터 성장
- 여름: 사망한 나무를 양분으로
  - 양분 += each 사망한 나무 나이 // 2
- 가을: 나무 번식
  - 인접한 8개의 칸에 나이가 1인 나무 생성
- 겨울: 양분 추가
  - 양분 += A[r][c]

제한 조건

변수 범위
- N ≤ 10 (땅 크기)
- M ≤ 100 (초기 나무 수)
- K ≤ 1000 (년 수)
- A[r][c] < 100 (매년 추가되는 양분)
시간: 0.3초 ⇒ 약 30,000,000 연산
메모리: 512MB ⇒ 약 128,000,000 개의 int

2. 시도

❌ 1차 시도: 배열
- Tree 정보를 각 땅별로, 양분 우선순위를 가지고 저장하려다 보니까 자료구조가 너무 복잡해짐 → List<List<PriorityQueue<>>>
**❌ 2차 시도: 우선순위 큐
- 트리 정보를 꼭 땅별로 저장할 필요 없음 → 전체 나무를 (양분: 위치) 형식으로 우선순위 큐에 저장
- 봄에는 나무 리스트를 한바퀴 돌면서 값을 변경해야하는데 우선순위 큐는 자동으로 작은 양분부터 나오기 때문에, 계속 같은 나무를 pop하는 오류를 범할 수 있음.
- 또한 전체 정렬되는 구조도 아니기 때문에 순회를 하면서 하나씩 변경한다면, 우선순위 큐를 쓰는 의미가 없고 무엇보다 오류가 발생할 것.
**✅ 3차 시도: deque
- 처음 한번만 정렬을 하고, pop push하면서 나무 나이 +1 씩 하거나, push 하지 않음(사망)
- 정렬된 순서를 유지할 수 있고, 순회하면서 필요 없는건 간단히 버릴 수 있으며, 맨앞에 요소를 추가하기도 좋음

3. 풀이 및 코드 (Solution)

import java.io.*;  
import java.util.*;  
  
public class Main {  
    static int N,M,K;  
    static int[][] A, land;  
    static Deque<Tree> trees;  
    static Deque<Tree> dead_trees = new ArrayDeque<>();  
    static Deque<Tree> new_trees = new ArrayDeque<>();  
    static int[][] ofs = new int[][] {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}};  
  
    static class Tree implements Comparable<Tree>{  
        int x, y, age;  
  
        public Tree(int x, int y, int age) {  
            this.x = x;  
            this.y = y;  
            this.age = age;  
        }  
  
  
        @Override  
        public int compareTo(Tree o) {  
            return this.age-o.age;  
        }  
    }  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
  
        String[] temp = br.readLine().split(" ");  
        N = Integer.parseInt(temp[0]);  
        M = Integer.parseInt(temp[1]);  
        K = Integer.parseInt(temp[2]);  
  
        A = new int[N][N];  
        land = new int[N][N];  
        for (int r=0; r<N; r++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            for (int c=0; c<N; c++) {  
                A[r][c] = Integer.parseInt(st.nextToken());  
                land[r][c] = 5;  
            }  
        }  
  
        int x,y,z;  
        List<Tree> temp_list = new ArrayList<>();  
        for (int m=0; m<M; m++) {  
            temp = br.readLine().split(" ");  
            x = Integer.parseInt(temp[0])-1;  
            y = Integer.parseInt(temp[1])-1;  
            z = Integer.parseInt(temp[2]);  
  
            temp_list.add(new Tree(x,y,z));  
        }  
  
        Collections.sort(temp_list);  
        trees = new ArrayDeque<>(temp_list);  
  
  
        // 시뮬레이션  
        Tree tree;  
        int age;  
        // K > 0 일 때까지 반복  
        for (int k=0; k<K; k++) {  
            // 봄  
            // M 값 수정  
            M = trees.size();  
  
            for (int m=0; m<M; m++){  
                tree = trees.poll();  
                x = tree.x;  
                y = tree.y;  
                age = tree.age;  
  
                if (land[x][y] >= age){ // - 양분 / + 나이 후 push                    land[x][y] -= age;  
                    tree.age += 1;  
                    trees.offer(tree);  
  
                    if (tree.age % 5 == 0){  
                        new_trees.offer(tree);  
                    }  
  
                } else {                // 여름 작업을 위해 죽은 나무 추가.  
                    dead_trees.offer(tree);  
                }  
            }  
  
            // 여름: 사망한 나무 -> 양분  
            while (!dead_trees.isEmpty()) {  
                tree = dead_trees.poll();  
                x = tree.x;  
                y = tree.y;  
                age = tree.age;  
  
                land[x][y] += age/2;  
            }  
  
            // 가을: 나무 번식  
            while (!new_trees.isEmpty()){  
                tree = new_trees.poll();  
                x = tree.x;  
                y = tree.y;  
  
                for (int[] o: ofs) {  
                    int nx = x + o[0];  
                    int ny = y + o[1];  
  
                    if (nx>=0 && nx<N && ny>=0 && ny<N) {  
                        trees.offerFirst(new Tree(nx, ny, 1));  // 맨 앞에 넣어서 정렬 맞춰줘야함.  
                    }  
                }  
            }  
  
            // 겨울: 양분 +            for (int r=0; r<N; r++) {  
                for (int c=0; c<N; c++) {  
                    land[r][c] += A[r][c];  
                }  
            }  
        }  
  
        System.out.println(trees.size());  
    }  
}

시간 복잡도: $O (K \times (T ree C n t + N^{2}))$
- 1년
  - 봄: 현재 나무 수
  - 여름: 죽은 나무수
  - 가을: 5의 배수 나이의 나무수 * 8
  - 겨울: N
- TreeCnt
  - 나무 유지비 없다면 → 땅별로 백개의 초기 나무가 매번 번식 = $N^{2} \times K \times 100 \times 8$
  - 나무 유지비가 매년 100씩 추가된다면 유지할 수 있는 최대 번식 가능한 나무 → 대략 25그루
  - ⇒ 약 $N^{2} \times K \times 25 \times 8 = 20, 000, 000$
  - 2천만 → 러프하게 잡은 거라 여유 있을 듯?
공간 복잡도: $O (N^{2} + T ree C n t)$ < 512MB
자료형: int 가능
- 1000년 후 최대 양분: $5 + 100 \times 1, 000 = 100, 005$
- 1000년 후 최대 나무 나이: $10 + 1, 000$

4. 회고 (Retrospective)

간만에 자바로 긴 코드 쓰려니까 너무 너무 헷갈리더라
- 커스텀 class에 대해 Collections.sort()나 Arrays.sort() 쓰려면 class에 compareTo 만들어줘야함
  - implements Comparable<T>도 잊지 말기
  - 혹은 매개변수로 (o1, o2) → o1.x - o2.x 이런식으로 규칙 넘겨주면 됨.
- Deque
  - 주로 ArrayDeque 사용
  - offer()(offerLast()) / offerFirst()
  - poll() (=pollFirst()) / pollLast()
  - peek() (=peekFirst()) / peekLast()
  - 걍 기본이 Queue(FIFO)라고 생각하면 됨.
여러가지 기준에 대해서 생각하기
- 문제가 땅으로 시작해서 막연히 땅이 중요한 조건이라고 생각할 수 있지만 사실 이 문제는 나무가 문제였음
- 땅을 기준으로 자료구조를 짜고 탐색을 하는 건 많이 해봐서 익숙한데 그게 능사가 아님.
- 자료구조가 너무 복잡하면, 불필요한 요소(기준)이 들어가지는 않았는지, 새로운 기준이 없는지 생각해보자.
자료구조의 특징에 대해서 잘 숙지하고 이해하기. 주로 언제 사용되는지, 어떤 때 사용하면 유용한지 등.
- Deque의 경우 정렬된 순서를 유지할 수 있고, 순회하면서 필요 없는건 간단히 버릴 수 있으며, 맨앞에 요소를 추가하기도 좋음
- LinkedList도 동일하나, 데이터 마다 pointer들을 저장해야해서 메모리적으로 좋지 않고, 캐시적으로도 공간지역성을 사용할 수 없다는 단점이 있음 → AI 설명이라 정확한지 따져봐야함.

Computer PS

☀️ Log

1. 문제 이해

핵심 요구사항

제한 조건

2. 시도

3. 풀이 및 코드 (Solution)

4. 회고 (Retrospective)

탐색기

목차