[백준] 16235 나무 재테크

1. 문제

www.acmicpc.net/problem/16235

16235번: 나무 재테크

2. 접근방법

복잡한 시뮬레이션 문제

 

봄 여름 가을 겨울로 나누어

 

4가지 상황에 대해 구현하여 나무를 K년동안 키워서

 

남아있는 나무의 갯수를 세는 문제.

우선 양분을 저장해둘 맵 배열이 필요하고

 

나무 하나하나를 저장해둘 우선순위  큐를 만들었다.

 

우선순위 큐인 이유는 봄에 나이가 가장 어린 나무 부터 양분을 먹고 자라기 때문에

쉽게 꺼내 쓰기 위해 우선순위큐를 이용하였다.

 

그런데 계속 나무들을 큐에 전부 꺼내서 작업하고 다시 다 집어넣고 하니깐

통과는 되지만 시간이 많이 걸리더라 어레이리스트에 저장하고 봄에만 정렬시켜서 쓰는 것이 조금 더 효율적일 것 같다.

 

여름은 봄에 죽은 나무들을 미리 저장해놨다가 양분 맵에 추가 시켜주면 되고

 

가을은 나이가 5의 배수인 나무들 찾아서 8방에 씨 뿌려주면 되고

 

겨울은 미리 주어진 양분의 양들만큼 양분 맵에 추가 시켜주면 된다.

 

봄 말고는 딱히 어려울것이 없으니 구현해보자

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class P16235나무재테크 {
	static class tree implements Comparable<tree> {
		int age;
		int row;
		int col;

		public tree(int age, int row, int col) {
			this.age = age;
			this.row = row;
			this.col = col;
		}

		@Override
		public int compareTo(tree o) {
			// TODO Auto-generated method stub
			return this.age - o.age;
		}

	}

	static int N, M, K, A[][], food[][];
	static PriorityQueue<tree> treeQue;
	static PriorityQueue<tree> deathQue = new PriorityQueue<tree>();

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

		N = Integer.parseInt(st.nextToken()); // 크기
		M = Integer.parseInt(st.nextToken()); // 나무 갯수
		K = Integer.parseInt(st.nextToken()); // k년후 나무 갯수

		A = new int[N][N];

		food = new int[N][N];

		for (int i = 0; i < N; i++)
			Arrays.fill(food[i], 5);
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				A[i][j] = Integer.parseInt(st.nextToken());
		}
		treeQue = new PriorityQueue<tree>();
		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());

			treeQue.add(new tree(z, x, y));
		}

		for (int i = 0; i < K; i++) {
			spring();
			summer();
			fall();
			winter();
		}
		
		System.out.println(treeQue.size());

	}

	static void spring() {
		PriorityQueue<tree> temp = new PriorityQueue<tree>();
		
		while (!treeQue.isEmpty()) {
			tree now = treeQue.poll();
			if (now.age > food[now.row][now.col]) {
				deathQue.offer(now);
				continue;
			}
			food[now.row][now.col] -= now.age;
			temp.offer(new tree(now.age + 1, now.row, now.col));
		}
		treeQue = temp;
	}

	static void summer() {
		while (!deathQue.isEmpty()) {
			tree now = deathQue.poll();
			food[now.row][now.col] += now.age / 2;
		}
	}

	static void fall() {
		int dr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
		int dc[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
		PriorityQueue<tree> temp = new PriorityQueue<tree>();

		while (!treeQue.isEmpty()) {
			tree now = treeQue.poll();
			temp.offer(now);
			if (now.age % 5 == 0) {
				for (int i = 0; i < 8; i++) {
					int row = now.row + dr[i];
					int col = now.col + dc[i];
					if (row < 0 || col < 0 || row >= N || col >= N)
						continue;
					temp.offer(new tree(1, row, col));
				}
			}

		}
		treeQue = temp;
	}

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

		}
	}
}

4. 마치며

생각보다 구현할 부분이 많아서 당황스러웠던 문제.

하지만 모든 시뮬레이션이 그렇듯 천천히 차근차근 진행하면 다 풀린다.