[BOJ] 16235 나무재테크 - JAVA

1. 문제

16235번: 나무 재테크

봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. 각각의 나무는 나무가 있는 1×1 크기의 칸에 있는 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다. 만약, 땅에 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.

여름에는 봄에 죽은 나무가 양분으로 변하게 된다. 각각의 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.

가을에는 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 어떤 칸 (r, c)와 인접한 칸은 (r-1, c-1), (r-1, c), (r-1, c+1), (r, c-1), (r, c+1), (r+1, c-1), (r+1, c), (r+1, c+1) 이다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않는다.

겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다. 각 칸에 추가되는 양분의 양은 A[r][c]이고, 입력으로 주어진다.

K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하시오.

---

2. 풀이

static 변수

A는 겨울에 더할 양분값 배열, map은 현재 밭의 양분 양을 담은 배열이다.

죽은 나무 저장할 queue, 나이가 5의 배수인 나무 저장할 queue, 전체 나무를 저장할 deque을 만들었다.

static int N, M, K;
static int[][] A;
static int[][] map;
static Queue<Tree> dead = new ArrayDeque<>();
static Queue<Tree> multiple5 = new ArrayDeque<>();
static Deque<Tree> trees = new ArrayDeque<>();
static int[][] deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

 

Tree 클래스

위치와 나이를 담았다. 

private static class Tree {
   int r, c, age;

   Tree(int r, int c, int age) {
      this.r = r;
      this.c = c;
      this.age = age;
   }
}

 

메인

기본 양분값이 5이므로 map을 5로 채웠다. 입력값 tree는 trees 덱에 담았다.

K만큼 계절을 반복한 뒤 마지막에 trees의 사이즈를 출력했다.

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

   N = Integer.parseInt(st.nextToken());
   M = Integer.parseInt(st.nextToken());
   K = Integer.parseInt(st.nextToken());

   A = new int[N + 1][N + 1];
   map = new int[N + 1][N + 1];

   for(int i=1;i<=N;i++){
      Arrays.fill(map[i],5);
   }

   for (int i = 1; i <= N; i++) {
      st = new StringTokenizer(in.readLine());
      for (int j = 1; j <= N; j++) {
         A[i][j] = Integer.parseInt(st.nextToken());
      }
   }

   for (int i = 0; i < M; i++) {
      st = new StringTokenizer(in.readLine());
      trees.offerFirst(new Tree(Integer.parseInt(st.nextToken()),
            Integer.parseInt(st.nextToken()),
            Integer.parseInt(st.nextToken())));
   }

   for(int i=0;i<K;i++){
      season();
   }

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

 

계절

나이가 어린 나무부터 양분을 먹는다는 구절 때문에 정렬이 꼭 필요하다고 생각할 수 있다. 하지만 문제에서 입력으로 주어지는 나무의 위치는 모두 서로 다르다고 했기 때문에 한 살 나이가 들 때 뒤에 넣고, 새로 생긴 나무들은 앞에 넣는다면 필요한만큼 최소한의 정렬이 된다.

 

봄

현재 trees 덱의 사이즈를 미리 구한 뒤 그 사이즈만큼만 반복한다.

양분이 모자라다면 죽은 나무를 모으는 큐에 넣는다.

양분이 충분하다면 map에서 양분을 빼고 나무의 나이를 더한다. 나이를 먹은 나무를 덱의 마지막에 다시 넣는다.

만약 한살 더 먹은 나이가 5의 배수라면 5배수나무를 모으는 큐에 넣는다.

 

여름

죽은 나무 큐가 빌 때까지 해당 위치에 나이/2만큼의 양분을 더한다.

 

가을

5배수 나무 큐가 빌 때까지 8방탐색을 한다. 범위에 벗어나지 않았다면 그 위치에 새 나무를 심어야 한다.

새 나무는 덱의 앞에 넣는다.

 

겨울

map에 A값을 하나씩 넣는다.

 

코드

private static void season(){
   //봄
   Tree now;
   int size = trees.size();
   for(int i=0;i<size;i++){
      now = trees.poll();
      if(map[now.r][now.c]<now.age){
         //죽은거
         dead.offer(now);
      }else{
         //산거
         map[now.r][now.c] -= now.age;
         now.age++;
         trees.offerLast(now);
         if(now.age%5==0) multiple5.offer(now);
      }
   }

   //여름
   Tree tree;
   while(!dead.isEmpty()){
      tree = dead.poll();
      map[tree.r][tree.c] += tree.age/2;
   }

   //가을
   int nr,nc;
   while(!multiple5.isEmpty()){
      tree = multiple5.poll();
      for(int d=0;d<8;d++){
         nr = tree.r+deltas[d][0];
         nc = tree.c+deltas[d][1];
         if(nr<1||nr>N||nc<1||nc>N) continue;
         trees.offerFirst(new Tree(nr,nc,1));
      }
   }

   //겨울
   for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
         map[i][j] += A[i][j];
      }
   }

}

---

3. 결과

덱으로 하지 않고 PriorityQueue를 썼다가 시간초과가 났다.