[backjoon]16235 나무재테크 java

www.acmicpc.net/problem/16235

16235번: 나무 재테크

 

일반적인 시뮬레이션에 정렬기능이 추가된 문제다.

순서대로 풀이하다가 봄 부분에서 정렬을 해주는 것이 포인트인 문제.

정렬부분에서 상당히 애먹었는데, 우선순위 큐로 풀었더니 시간초과가 났는지 바로 틀렸습니다. 가 떴다.

그래서 Tree라는 구조체를 만들어서 age기준으로 정렬하여 수행하였다.

시간을 주의 깊게 봐야겠다.

 

import java.io.*;
import java.util.*;

class Main {
	static int N ,M, K;
	static int[][] A, ground;
	static ArrayList<Tree> fallTree;
	static ArrayList<Tree> trees = new ArrayList<>();
	static ArrayList<Tree> liveTrees, deadTrees;
	static int[][] dirs = {{-1,-1},{-1,0},{-1,1}, {0, -1}, {0, 1}, {1, -1}, {1, 0},{1, 1}};
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
 
		A = new int[N][N];
		ground = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int cur = Integer.parseInt(st.nextToken());
				A[i][j] = cur;
				ground[i][j] = 5;
			}
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			int z = Integer.parseInt(st.nextToken());
			trees.add(new Tree(x, y, z));
		}

		while(K-- > 0) {
			//자신의 나이만큼 양분을 먹고 자란다., 여러대 나무가 있을 수 있고, 어린 것 부터 먹고 못 먹으면 죽음
			//죽은 나무 나이의 절반이 양분이 됨
			liveTrees = new ArrayList<>();
			deadTrees = new ArrayList<>();
			fallTree = new ArrayList<>();
			Collections.sort(trees);
			springSummer();
			
			//나무가 번식 나무의 나이가 5배수여야함. 인접한 8방면 칸에 나이가 1인 나무가 생김 벗어나는 부분은 나무 안 생김
			fall();
			//입력으로 주어지는 양분이 추가로 땅에 주어진다.
			winter();
		}
		System.out.println(trees.size());
	}

	
	public static void winter() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ground[i][j] += A[i][j];
			}
		}
	}
	/**
	 * 나무가 번식
	 * 1. 번식하는 나무는 나이가 5의 배수
	 * 2. 인접한 8개의 칸에 나이가 1인 나무 심는다. 
	 * 3. 벗어나는 칸에는 나무가 생기지 않는다.
	 * **/
	public static void fall() {
		int cnt= 0;
		for(Tree tree : fallTree) {
			for(int dir = 0; dir < 8; dir++) {
				int nextR = tree.row + dirs[dir][0];
				int nextC = tree.col + dirs[dir][1];
				if(nextR < 0 || nextC < 0 || nextR >= N || nextC >= N) continue;
				cnt++;
				trees.add(new Tree(nextR, nextC, 1));
			}
		}
	}
	
	/** 
	 * 1. 나무가 자신의 나이만큼 양분을 먹는다.
	 * 2. 나이가 1 증가한다.
	 * 3. 각자 칸에 있는 양분만 먹는다.
	 * 4. 나이가 어린 것 부터 먹는다.(우선순위 큐 이용)
	 * 5. 양분이 부족하다면 바로 죽는다.(새로운 큐에 넣지 않고, 죽은 나무의 나이는 따로 더한다.
	 * **/
	public static void springSummer() {
		
		for (Tree tree : trees) {
			int row = tree.row;
			int col = tree.col;
			int age = tree.age;
			
			int nutrient = ground[row][col];
			if(nutrient >= age) {
				 ground[row][col] -= age;
				 liveTrees.add(new Tree(row, col, age+1));
				 if((age+1) %5== 0) {
					 fallTree.add(new Tree(row, col, age));
				 }
			 }else {
				 deadTrees.add(tree);
			 }
		}

		for (Tree t : deadTrees) {
			int row = t.row;
			int col = t.col;
			int age = t.age;
			ground[row][col] += (age/2);
		}
		
		trees.clear();
		trees.addAll(liveTrees);
	}
}
class Tree implements Comparable<Tree>{
	int row;
	int col;
	int age;
	Tree(int row, int col, int age){
		this.row = row;
		this.col = col;
		this.age = age;
	}
	@Override
	public int compareTo(Tree o) {
		// TODO Auto-generated method stub
		return this.age - o.age;
	}
}

 

 

 

시간초과 났지만 우선순위 큐를 이용한 방법은 더보기

import java.io.*;
import java.util.*;

class test {
	static int N ,M, K;
	static int[][] A, ground;
	static Queue<Dot> fallTree;
	static Queue<Integer>[][] trees;
	static int[][] dirs = {{-1,-1},{-1,0},{-1,1}, {0, -1}, {0, 1}, {1, -1}, {1, 0},{1, 1}};
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		//땅
		A = new int[N][N];
		ground = new int[N][N];
		trees = new Queue[N][N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int cur = Integer.parseInt(st.nextToken());
				A[i][j] = cur;
				ground[i][j] = 5;
				trees[i][j] = new LinkedList<Integer>();
			}
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			trees[x-1][y-1].add(z);
		}

		while(K-- > 0) {
			//자신의 나이만큼 양분을 먹고 자란다., 여러대 나무가 있을 수 있고, 어린 것 부터 먹고 못 먹으면 죽음
			//죽은 나무 나이의 절반이 양분이 됨
			springSummer();
			
			//나무가 번식 나무의 나이가 5배수여야함. 인접한 8방면 칸에 나이가 1인 나무가 생김 벗어나는 부분은 나무 안 생김
			fall();
			//입력으로 주어지는 양분이 추가로 땅에 주어진다.
			winter();
		}
		System.out.println(count());
	}
	
	public static int count() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cnt += trees[i][j].size();
			}
		}
		return cnt;
	}
	
	public static void winter() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ground[i][j] += A[i][j];
			}
		}
	}
	/**
	 * 나무가 번식
	 * 1. 번식하는 나무는 나이가 5의 배수
	 * 2. 인접한 8개의 칸에 나이가 1인 나무 심는다. 
	 * 3. 벗어나는 칸에는 나무가 생기지 않는다.
	 * **/
	public static void fall() {
		int cnt= 0;
		for(Dot tree : fallTree) {
			for(int dir = 0; dir < 8; dir++) {
				int nextR = tree.row + dirs[dir][0];
				int nextC = tree.col + dirs[dir][1];
				if(nextR < 0 || nextC < 0 || nextR >= N || nextC >= N) continue;
cnt++;
				trees[nextR][nextC].add(1);
			}
		}
		System.out.println(cnt);
	}
	
	/** 
	 * 1. 나무가 자신의 나이만큼 양분을 먹는다.
	 * 2. 나이가 1 증가한다.
	 * 3. 각자 칸에 있는 양분만 먹는다.
	 * 4. 나이가 어린 것 부터 먹는다.(우선순위 큐 이용)
	 * 5. 양분이 부족하다면 바로 죽는다.(새로운 큐에 넣지 않고, 죽은 나무의 나이는 따로 더한다.
	 * **/
	public static void springSummer() {
		fallTree = new LinkedList<Dot>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				 Queue<Integer> curTree = trees[i][j];
				 PriorityQueue<Integer> resultTree = new PriorityQueue<>();
				 
				 int deadTreeAge = 0;
				 for(int age : curTree) {
					 int nutrient = ground[i][j];
					 if(nutrient >= age) {
						 ground[i][j] -= age;
						 resultTree.add(age+1);
						 if((age+1) %5== 0) {
							 fallTree.add(new Dot(i, j));
						 }
					 }else {
						 deadTreeAge += (age/2);
					 }
				 }
				 
				 ground[i][j] += deadTreeAge;
				 trees[i][j] = resultTree;
			}
		}
	}
}
class Dot{
	int row;
	int col;
	Dot(int row, int col){
		this.row = row;
		this.col = col;
	}
}