https://www.acmicpc.net/problem/16235
크기는 N X N
모든 칸은 양분이 5가 기본으로 있음.
나무가 자신의 나이만큼 양분을 먹는다 -> 먹으면 나이가 1 증가
한 땅에 여러개의 나무가 심어져있을 수 있음.
여러개일 경우 나무의 나이가 어린순으로 양분을 먼저 먹는다.
사계절이 존재함.
봄 : 나이만큼 양분을 먹는다.먹으면 나이+1 못먹는 나무는 죽음.
여름 : 봄에 죽은 나무들이 양분으로 변함(여기서 계산해서 칸에 양분 추가.)
가을 : 나무가 번식한다. 나무의 나이가 5의배수이면 가능하다. 인접 8칸에 나이가 1인 나무가 생김.
겨울 : 기계가 각 땅에 양분을 추가. -> 각 땅의 양분만큼 추가된다.
K년이 지난후 -> 0년부터 K까지 반복문돌면됨.
결과는 살아있는 나무의 개수
살아있는 나무와 죽은 나무를 분리해서 계산해야함.
죽은 나무는 여름에 양분이 되야하고
살아있는 나무는 봄에 나이를 먹어야하기 때문에.
사계절 코드를 그대로 구현하면된다.
그후 새로 생기는 나무들은 deque의 addFirst를 통해서 맨앞에 넣어줌으로써 나이순이 계속 유지되게 해준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
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 IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] map = new int[N+1][N+1];
int[][] eat = new int[N+1][N+1];
Deque<Tree> tree_list = new ArrayDeque<>();
List<Tree> list = new ArrayList<>();
//기본 입력으로 주어지는거 넣어주기.
for(int row = 1; row <=N;row++){
st= new StringTokenizer(br.readLine());
for(int col=1;col<=N;col++){
map[row][col] = Integer.parseInt(st.nextToken());
eat[row][col] = 5;
}
}
for(int idx =1 ;idx <=M;idx++){
st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
int age = Integer.parseInt(st.nextToken());
list.add(new Tree(row,col,age));
}
//처음 나무 나이순 정렬
Collections.sort(list);
for(Tree t : list){
tree_list.offer(t);
}
while(K-->0){
Queue<Tree> tree_die = new LinkedList<>();
//봄
for(int idx = 0; idx <tree_list.size();){
Tree cur = tree_list.poll();
if(eat[cur.row][cur.col] >= cur.age){
eat[cur.row][cur.col] -= cur.age;
cur.age+=1;
idx++;
tree_list.add(cur);
}else{
tree_die.offer(cur);
}
}
//여름
for(Tree tree : tree_die){
eat[tree.row][tree.col] += tree.age/2;
}
//가을
Queue<Tree> temp = new LinkedList<>();
//5의배수를 만족하면 넣어놓음.
for(Tree tree : tree_list){
if(tree.age % 5 == 0){
temp.offer(tree);
}
}
while(!temp.isEmpty()){
Tree t = temp.poll();
for(int idx= 0 ; idx <8;idx++){
int nxt_row = t.row + dx[idx];
int nxt_col = t.col + dy[idx];
if(nxt_row > 0 && nxt_row <= N && nxt_col >0 && nxt_col <= N){
tree_list.addFirst(new Tree(nxt_row,nxt_col,1));
}
}
}
//겨울
for(int row =1 ;row <=N;row++){
for(int col=1 ;col<=N;col++){
eat[row][col] += map[row][col];
}
}
}
System.out.println(tree_list.size());
br.close();
}
public static class Tree implements Comparable<Tree>{
int row;
int col;
int age;
public Tree(int row, int col, int age) {
this.row = row;
this.col = col;
this.age = age;
}
@Override
public int compareTo(Tree o) {
return this.age - o.age;
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
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 IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] map = new int[N+1][N+1];
int[][] eat = new int[N+1][N+1];
Queue<Tree> tree_list = new PriorityQueue<>();
//기본 입력으로 주어지는거 넣어주기.
for(int row = 1; row <=N;row++){
st= new StringTokenizer(br.readLine());
for(int col=1;col<=N;col++){
map[row][col] = Integer.parseInt(st.nextToken());
eat[row][col] = 5;
}
}
for(int idx =1 ;idx <=M;idx++){
st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int col = Integer.parseInt(st.nextToken());
int age = Integer.parseInt(st.nextToken());
tree_list.offer(new Tree(row,col,age));
}
while(K-->0){
Queue<Tree> tree_die = new LinkedList<>();
//봄
for(int idx = 0; idx <tree_list.size();){
Tree cur = tree_list.poll();
if(eat[cur.row][cur.col] >= cur.age){
eat[cur.row][cur.col] -= cur.age;
cur.age+=1;
idx++;
tree_list.add(cur);
}else{
tree_die.offer(cur);
}
}
//여름
for(Tree tree : tree_die){
eat[tree.row][tree.col] += tree.age/2;
}
//가을
Queue<Tree> temp = new LinkedList<>();
//5의배수를 만족하면 넣어놓음.
for(Tree tree : tree_list){
if(tree.age % 5 == 0){
temp.offer(tree);
}
}
while(!temp.isEmpty()){
Tree t = temp.poll();
for(int idx= 0 ; idx <8;idx++){
int nxt_row = t.row + dx[idx];
int nxt_col = t.col + dy[idx];
if(nxt_row > 0 && nxt_row <= N && nxt_col >0 && nxt_col <= N){
tree_list.offer(new Tree(nxt_row,nxt_col,1));
}
}
}
//겨울
for(int row =1 ;row <=N;row++){
for(int col=1 ;col<=N;col++){
eat[row][col] += map[row][col];
}
}
}
System.out.println(tree_list.size());
br.close();
}
public static class Tree implements Comparable<Tree>{
int row;
int col;
int age;
public Tree(int row, int col, int age) {
this.row = row;
this.col = col;
this.age = age;
}
@Override
public int compareTo(Tree o) {
return this.age - o.age;
}
}
}