[Algorithm] 백준_15235 나무 재테크 java

문제

N*N의 땅에 M개의 나무를 심는다. 한 칸에는 여러개의 나무가 심어질 수도 있다. 사계절을 보내면서 각 계절에 맞는 과정을 반복한다. 과정을 반복하며 K년이 지났을 때 살아있는 나무의 개수를 출력하면 되는 문제이다.

풀이

사계절에 맞는 함수를 만들어서 년수만큼 반복했다.
trees 연결리스트에 M개의 나무를 관리한다.

• spring() : trees에 있는 나무를 하나씩 빼서 나이가 양분의 값보다 크면 양분의 값에서 나이를 빼고, 나이를 +1 한다. 아니면 life를 0d으로 변경해 죽었음을 식별한다.
• summer() : trees에 있는 값을 iterator로 순회하며 life가 0인 경우 /2 한 후 양분에 더하기 해준다. 그리고 remove 한다
  원래 iterator로 하지 않고 deadTrees 연결리스트에 죽은 나무를 관리해 삭제했었는데, concurrentmodificationexception 오류도 나고, 시간초과가 나서 Iterator 사용으로 변경했다.
• fall() : 나무의 나이가 5의 배수인 것들의 인접칸을 trees에 추가한다.
  addAll(0, 추가할 리스트)를 하면 인덱스 0번부터 추가된다. 이렇게 하면 나이가 적은 순으로 정렬이 필요없어진다.
• winter() : 입력받은 배열 값을 양분으로 추가한다.

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class BOJ_16235 {
    static int N;
    static int M;
    static int K;
    static int[][] map;
    static int[][] nutr;
    static LinkedList<Tree> trees = new LinkedList<>();
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void main(String[] args) throws Exception{
        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];
        nutr = 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] = Integer.parseInt(st.nextToken()); //겨울에 추가되는 양분 값
                nutr[i][j] = 5; //기본 양분값
            }
        }

        // 나무 정보
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());

            trees.add(new Tree(x, y, n, 1));
        }

        for (int i = 0; i < K; i++) {
            spring();
            summer();
            fall();
            winter();
        }

        System.out.println(trees.size());
    }

    static void spring() {
        for (Tree t : trees) {
            if (nutr[t.x][t.y] >= t.age) {
                nutr[t.x][t.y] -= t.age;
                t.age++;
            } else {
                t.life = 0;
            }
        }
    }

    /*
    * 원래 deadTrees LinkedList 새로 만들고, trees에서 삭제하는 방식을 썼었는데 시간초과남
    * iterator 사용으로 해결 완료
    * iterator 사용 시 반복문을 순환하는 동안 컬렉션을 안전하게 사용할 수 있음.
    * */
    static void summer() {
        for (Iterator<Tree> itt = trees.iterator(); itt.hasNext();) {
            Tree t = itt.next();
            if (t.life == 0) {
                int n = t.age / 2;
                nutr[t.x][t.y] += n;

                itt.remove();
            }
        }
    }

    static void fall() {
        LinkedList<Tree> newTrees = new LinkedList<>();
        for (Tree t : trees) {
            if (t.age % 5 == 0) {
                for (int j = 0; j < 8; j++) {
                    int nx = t.x + dx[j];
                    int ny = t.y + dy[j];

                    if (nx > 0 && nx <= N && ny > 0 && ny <= N ) {
                        newTrees.add(new Tree(nx, ny, 1, 1));
                    }
                }
            }
        }
        trees.addAll(0, newTrees);
    }

    static void winter() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                nutr[i][j] += map[i][j];
            }
        }
    }

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

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

후기 👀

시간 초과는 정말.. 뭐 때문에 나는지 찾기가 애매한 것 같다. 어느정도 감은 오지만ㅠㅠ
추측으로 정렬이나 add, remove 연산과 같은 부분일 것 같다라고 가정해서 해결은 했지만, 뭔가 정확한 단서가 있었으면 좋겠다. 어떻게 공부하면 될까?!