16235 나무 재테크 - 삼성 sw 역량 기출
N * N 의 땅에 M개의 나무를 심었다.
기본 양분의 값은 모두 5로 동일하다.
봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
한 칸에 여러 나무가 있다면 나이가 어린 나무부터 양분을 먹는다.
양분이 부족하면 나무는 즉시 죽는다.
여름에는 봄에 죽은 나무가 양분으로 변한다. 죽은 나무 나이 / 2 가 양분으로 변한다.
가을에는 나무의 나이가 5의 배수이면 인접한 8개의 칸으로 번식을 한다.
번식한 나무의 나이는 1이다.
겨울에는 주어진 A[][] 만큼 양분이 추가 된다.
K년이 지난 후 살아 있는 나무의 개수는?
입력
-
겨울에 추가 될 양분은
A[][]로 받는다. - 나무의 좌표는 우선순위 큐를 이용해서 받는다.
- 나무를 list에 저장했으나 나이 순으로 정렬을 하면 시간초과가 난다.
- 봄에 양분을 먹는 나무를 어린 나무일 수 있도록 우선순위 큐를 사용한다.
- 현재 년도와 다음 년도를 번갈아가면서 입력하기 위해서 우선순위 큐를 두 개짜리 배열로 초기화한다.
- 양분을 저장할 이차원 배열
map[][]을 모두 5로 초기화한다.
구현
- 계절마다 함수를 구현한다.
- 봄에는 현재 나무들을 뽑아서 양분을 먹으면 살아있는 나무 큐와 내년 나무 큐에, 죽으면 죽은 나무 큐에 추가한다.
- 살아있는 나무 큐와 내년 나무 큐에는 나이를 1 증가시켜서 추가한다.
- 여름에는 map[][]에 죽은 나무 큐의 나이/2 를 더해준다.
- 가을에는 델타 배열을 사용하여 살아있는 나무 큐가 땅의 범위 내에서 번식할 수 있도록 한다.
- 현재 뽑은 큐와 번식된 나무들을 내년 큐에 넣어준다.
- 겨울에는 map에 A를 더해준다.
- 메인 함수에서 K만큼 계절을 반복한다.
nextYear = (thisYear+1)%2를 사용해 계속 반복되도록 설정해준다.- 각 해마다 살아있는 나무와 죽은 나무를 받을 큐를 생성해준다.
- 반복 마지막에
thisYear = nextYear로 다음 년도로 넘어갈 수 있도록 설정해준다.
- thisYear 우선순위 큐의 크기를 출력한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main나무재테크 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st1.nextToken()); // 맵 크기
int M = Integer.parseInt(st1.nextToken()); // 나무 개수
int K = Integer.parseInt(st1.nextToken()); // k년
int[][]A = new int[N][N];
for(int i = 0; i < N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < N; j++) {
A[i][j] = Integer.parseInt(st2.nextToken());
}
}
PriorityQueue<Tree>[] tree = new PriorityQueue[2];
tree[0] = new PriorityQueue<>();
tree[1] = new PriorityQueue<>();
int thisYear = 0;
int nextYear = 0;
for(int i = 0; i < M; i++) {
StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
tree[thisYear].add(new Tree(Integer.parseInt(st3.nextToken())-1, Integer.parseInt(st3.nextToken())-1, Integer.parseInt(st3.nextToken())));
}
int[][]map = new int[N][N];
for(int i = 0; i < N; i++) {
Arrays.fill(map[i], 5);
}
while(true) {
if(K == 0) {
break;
}
nextYear = (thisYear+1)%2;
Queue<Tree> live = new LinkedList<>();
Queue<Tree> die = new LinkedList<>();
spring(map, tree[thisYear], tree[nextYear], live, die);
summer(map, die);
fall(tree[nextYear], live);
winter(map, A);
thisYear = nextYear;
K--;
}
System.out.println(tree[nextYear].size());
}
static int N;
static int[] dy = {-1,-1,-1,0,0,1,1,1};
static int[] dx = {-1,0,1,-1,1,-1,0,1};
static void spring(int[][] map, PriorityQueue<Tree> thisYear, PriorityQueue<Tree> nextYear, Queue<Tree> live, Queue<Tree> die) {
while(!thisYear.isEmpty()) {
Tree tree = thisYear.poll();
if(map[tree.y][tree.x] >= tree.age) {
map[tree.y][tree.x] -= tree.age;
Tree next = new Tree(tree.y, tree.x, tree.age+1);
nextYear.add(next);
live.add(next);
}else {
die.add(tree);
}
}
}
static void summer(int[][] map, Queue<Tree> die) {
while(!die.isEmpty()) {
Tree tree = die.poll();
map[tree.y][tree.x] += tree.age/2;
}
}
static void fall(PriorityQueue<Tree> nextYear, Queue<Tree> live) {
while(!live.isEmpty()) {
Tree tree = live.poll();
if(tree.age%5 == 0) {
for(int i = 0; i < 8; i++) {
int yi = dy[i]+tree.y;
int xi = dx[i]+tree.x;
if(yi >= N || xi >= N || yi < 0 || xi < 0)continue;
nextYear.add(new Tree(yi, xi, 1));
}
}
}
}
static void winter(int[][] map, int[][] A) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
map[i][j] += A[i][j];
}
}
}
}
class Tree implements Comparable<Tree>{
int y;
int x;
int age;
Tree(int y, int x, int age){
this.y = y;
this.x = x;
this.age = age;
}
@Override
public int compareTo(Tree o) {
return this.age - o.age;
}
}