자바 - 백준 16235 / 나무 재테크

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

16235번: 나무 재테크

골드3

 

구현 방법

구현 문제라서 일단 문제의 조건을 간단하게 정리 했다.

1. n * n = 땅 크기

2. 처음 모든 칸 양분 5

3. m = 나무 개수

4. 봄 -> 자신의 나이만큼 양분 먹음 -> 나이 +1

5. 한칸에 여러개 나무 가능

6. 나이 어린 나무부터 양분 먹음, 양분 부족하면 바로 죽음

7. 여름 -> 죽은 나무 양분으로 변함, 나무 나이 // 2

8. 가을 -> 나무 나이 5의 배수면 번식, 인접한 8개에 한개씩 추가

9. 겨울 -> 양분 추가, A[r][c] 만큼 

10. k년 지난후 나무 개수는?

 

제한 사항은 다음과 같다

• 1 ≤ N ≤ 10
• 1 ≤ M ≤ N2
• 1 ≤ K ≤ 1,000
• 1 ≤ A[r][c] ≤ 100
• 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10
• 입력으로 주어지는 나무의 위치는 모두 서로 다름

제한 사항에 따른 시간 복잡도 계산

1. 년차에 따른 O(N)

2.  봄 - 나무 양분 주기에 따른 O(N) +

     여름 - 죽은 나무 양분으로 변경에 따른 O(N) +

     가을 - 나무 변식 여부 확인에 따른 O(N) +

     추가된 나무 반영에 따른 O(N) +

     겨울 - 양분 추가에 따른 O(N)

총 O(n^2)이라서 제한 사항에 따른 런타임 오류는 걱정 없다.

 

구현 순서는 위에 조건 요약한것 바탕으로 코드 작성 하면 된다. 여기서 주의할 점은 크게 3가지이다.

1. 처음 나무 정보를 받고나서, 나이순으로 정렬을 해야한다. 안하면 런타임 오류 생긴다.

2. 번식된 나무는 기존 나무 정보의 앞쪽에 추가한다. 이유는 나이 어린순으로 양분을 먹기 때문이다.

3. 새로 생성된 나무 add와 죽은 나무에 의한 remove를 list에 반영 할때 루프 안에서 하면 ConcurrentModificationException(동시성 문제) 문제가 생긴다. 이유는 루프 한 단계가 실행 될때마다 list의 인덱스가 달라져 무한 루프(add 경우)에 빠지거나 IndexOutOfBoundary(remove) 오류가 발생하기 때문이다.  따라서 remove와 add 처리는 루프 안에서 단순히 처리 하면 안된다. add의 경우 추가 list를 따로 생성하여 나중에 반영하는 방법를 이용하고, remove의 경우는 죽은 나무를 따로 check하는 변수를 만들거나, Iterator를 이용하여 index 자체를 삭제 하는 방법으로 구현해야 한다.

코드

package boj;

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

/**
 * 백준 16235
 * 나무 재테크
 * 골드3
 * https://www.acmicpc.net/problem/16235
 * 이 코드가 다른 코드보다 시간이 오래 걸리는 이유
 * 죽은 나무를 다루는 부분이 따로 없어서 죽은 나무가 자꾸 누적되어서  시간도 더 걸리고 용량도 더 많이 먹게 된다.
 * 이런 면에서 동적 할당이 정말 좋은게 용량을 쓰고 free 하면 되니까 결국 시간도 아끼도 용량도 아끼는 셈이 되네.
 */
public class Boj16235 {

    static class Tree {
        int x;
        int y;
        int age;

        boolean life;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //n 땅 크기, m 나무 개수, k 년
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        //현재  양분
        int[][] curA = new int[n][n];

        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                curA[i][j] = 5;
        }

        // 추가되는 양분 양
        int[][] a = new int[n][n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 위치 x, 위치 y, age
        List<Tree> trees = new ArrayList<>();

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            trees.add(new Tree(Integer.parseInt(st.nextToken()) - 1,
                    Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()), true));
        }

        Collections.sort(trees, (t1, t2) -> t1.age - t2.age);

        for(int year = 0; year < k; year++) {

            //봄
            for(Tree t : trees) {
                //죽은 나무
                if(!t.life)
                    continue;

                if(curA[t.x][t.y] < t.age) {
                    //양분 부족시 나무 죽음
                    t.life = false;
                } else {
                    curA[t.x][t.y] -= t.age;
                    t.age += 1;
                }
            }

            //여름
            for(Tree t : trees) {
                if(!t.life)
                    curA[t.x][t.y] += t.age / 2;
            }

            List<Tree> temp = new ArrayList<>();

            //가을
            for(Tree t : trees) {

                //죽은 나무
                if(!t.life)
                    continue;

                if(t.age % 5 == 0) {
                    if(t.x - 1 >= 0 && t.y - 1 >= 0)
                        temp.add(new Tree(t.x - 1, t.y - 1, 1, true));

                    if(t.x - 1 >= 0)
                        temp.add(new Tree(t.x - 1, t.y, 1, true));

                    if(t.x - 1 >=0 && t.y + 1 < n)
                        temp.add(new Tree(t.x - 1, t.y + 1, 1, true));

                    if(t.y - 1 >= 0)
                        temp.add(new Tree(t.x, t.y - 1, 1, true));

                    if(t.y + 1 < n)
                        temp.add(new Tree(t.x, t.y + 1, 1, true));

                    if(t.x + 1 < n && t.y - 1 >= 0)
                        temp.add(new Tree(t.x + 1, t.y - 1, 1, true));

                    if(t.x + 1< n)
                        temp.add(new Tree(t.x + 1, t.y, 1, true));

                    if(t.x + 1< n && t.y + 1< n)
                        temp.add(new Tree(t.x + 1, t.y + 1, 1, true));
                }
            }

            for(Tree t : trees) {
                if(t.life)
                    temp.add(t);
            }

            trees = temp;

            //겨울
            for(int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    curA[i][j] += a[i][j];
                }
            }
        }

        int answer = 0;

        for(Tree t : trees) {
            if(t.life)
                answer++;
        }

        System.out.println(answer);

    }
}

 

느낀 점

1. 웹 개발 공부 과정에서 처음 들은 단어인 동시성 문제의 예시를 알고리즘 공부하면서 만나서 이해하는데 많은 도움이 되었다.

2. 다른 분들의 코드에 비해서 실행 시간이 2배정도 오래 걸렸는데 이유를 찾는 과정에서 동적 할당의 장점을 경험 했다.

=> 내 코드의 경우 죽은 나무 처리를 위한 변수도 만들고, 실제 나무 리스트에도 삭제 나무를 실제로 지워서 시간이 많이 걸리고 용량도 더 많이 썼다. 이부분은 죽은 나무를 다루는 LinkedList를 만들어서 그때 그때 죽은 나무들의 리스트만 저장한 후, 추가할 양분 계산 후 poll 시키고, 실제 나무 리스트에서는 실제 삭제하지 않고, 죽은 나무 변수에 표시만 하는 식으로 하면 시간도 용량도 줄어들것이다.

 

참고 블로그

https://offbyone.tistory.com/170

루프 도중 안전하게 삭제하기