Baekjoon 16235 나무 재테크 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/16235
• 분류 :시뮬레이션, 우선순위 큐
• 풀이 시간 : 1시간 30분

문제 해설

1. N x N 크기의 땅이 있음
2. 처음에는 모든 땅에는 5만큼의 양분 존재
3. 땅은 양분와 여러 개의 나무가 존재
4. 나무의 사계절
   • 봄 : 나이가 어린 순서대로 자신의 나이만큼 땅의 양분 먹음 + 나이 1 증가
     • 나이만큼 못 양분 못 먹으면 죽음
   • 여름 : 봄에 죽은 나무의 나이 / 2 만큼 양분으로 변함
   • 가을 : 심어진 나무의 나이가 5의 배수이면 번식
     • 주위 8칸에 나이가 1인 나무 심음
   • 겨울 : 기계가 땅에 양분 추가
5. k년이 지난 후 남은 나무의 개수를 구하라

• A는 땅의 크기만큼 주어짐
  • map과 A의 배열 크기는 같음
  • 겨울이 되면 map[i][j] 에 A[i][j] 만큼의 양분이 추가됨

A 배열 자체가 이해가 안 돼서 애 좀 먹음..

처음엔 A가 일차원 배열이라 매 년 A[i]의 값이 모든 map에 추가되는 줄 알고 잘못 코딩했다..

Solution

풀이 접근 방법

1. 문제의 길이가 길고 단계별로 조건이 존재한다 = 거의 90% 확률로 시뮬레이션 문제 ...
2. 한 칸에 두 개의 정보(양분, 심어진 나무들)가 들어가야 함 = Land class 생성
3. 어린 나이 나무부터 양분 먹음 = 우선순위 큐 사용
4. 인접한 8칸으로 나무 생김 = dx, dy 사용

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main_16235 {
  static class Land {
    // 땅의 양분
    int food;
    // 1칸의 땅에 심긴 나무의 나이
    PriorityQueue<Integer> trees;

    // 객체 생성 시 모든 땅의 양분 5로 초기화
    public Land() {
      this.food = 5;
      trees = new PriorityQueue<Integer>();
    }

  }

  static int N, M, K;
  static int[][] A;
  static Land[][] map;
  // 번식 시 방문하는 8칸으로 이동하는 좌표
  static int[] dx = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy = { -1, 0, 1, -1, 1, -1, 0, 1 };

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String[] info = br.readLine().split(" ");

    N = Integer.valueOf(info[0]);
    M = Integer.valueOf(info[1]);
    K = Integer.valueOf(info[2]);
    A = new int[N][N];
    map = new Land[N][N];

    // 각 칸에 추가되는 양분의 양을 담은 배열 입력받음
    for (int i = 0; i < N; i++) {
      A[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    // 땅 지도 초기화
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        map[i][j] = new Land();
      }
    }

    for (int i = 0; i < M; i++) {
      info = br.readLine().split(" ");

      int x = Integer.valueOf(info[0]);
      int y = Integer.valueOf(info[1]);
      int value = Integer.valueOf(info[2]);

      // 나무 심기
      map[x - 1][y - 1].trees.add(value);
    }

    int treeCnt = 0;
    for (int i = 0; i < K; i++) {
      // 1년이 지날 때 마다 몇 그루의 나무가 살아있는지 구함
      treeCnt = oneYearFlow();

      // 살아있는 나무가 없으면 반복문 종료
      if (treeCnt == 0)
        break;
    }

    bw.write(treeCnt + " \n");
    bw.flush();
    bw.close();
  }

  static int oneYearFlow() {
    // 봄 + 여름
    int[][] breeding = springAndSummer();

    // 가을
    fall(breeding);
    // 겨울
    winter();

    return countAliveTree();
  }

  static int[][] springAndSummer() {
    // 각 칸에서 가을에 번식 가능한 나무의 수를 담을 배열
    int[][] breeding = new int[N][N];

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        // 양분 먹은 = 살아남은 나무를 담은 큐
        PriorityQueue<Integer> newTree = new PriorityQueue<>();
        Land land = map[i][j];
        // 번식 가능한 나무의 수
        int breedingCnt = 0;

        // 봄 - 나무 존재하고, 나이만큼 양분 먹을 수 있으면
        while (!land.trees.isEmpty() && land.food - land.trees.peek() >= 0) {
          int age = land.trees.poll();

          // 나이만큼 양분 먹음
          land.food -= age;
          // 나이 증가
          newTree.add(age + 1);

          // 가을 - 증가한 나이가 5의 배수이면 번식할 수 있음
          if ((age + 1) % 5 == 0) {
            breedingCnt += 1;
          }
        }

        // 큐가 비어있지 않음 = 양분 못먹은 나무 존재 = 죽어야 함
        // 여름 - 죽은 나무 양분으로 전환
        int summerFood = 0;
        while (!land.trees.isEmpty()) {
          summerFood += (int) Math.floor(land.trees.poll() / 2);
        }

        // 새로운 나무 정보 저장
        land.trees = newTree;

        // 죽은 나무 양분 저장
        land.food += summerFood;

        // 번식 가능한 나무 개수 저장
        breeding[i][j] = breedingCnt;
      }
    }

    return breeding;
  }

  static void fall(int[][] breeding) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (breeding[i][j] == 0)
          continue;

        // 번식 가능한 나무가 있으면
        // 주위 8칸으로 나무 번식
        for (int k = 0; k < 8; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k];
          int newTreeCnt = breeding[i][j];

          // 주위의 칸이 범위 밖이면 넘김
          if (!isIn(nx, ny))
            continue;

          // 번식 가능한 나무의 개수대로 나이가 1인 나무 심음
          while (newTreeCnt-- > 0) {
            map[nx][ny].trees.add(1);
          }
        }
      }
    }
  }

  static void winter() {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        map[i][j].food += A[i][j];
      }
    }
  }

  static int countAliveTree() {
    int alive = 0;

    // 큐의 사이즈 = 살아남은 나무의 수
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        alive += map[i][j].trees.size();
      }
    }

    return alive;
  }

  static boolean isIn(int x, int y) {
    if (0 <= x && x < N && 0 <= y && y < N) {
      return true;
    }
    return false;
  }

}