백준 16235번 <나무 재테크>

백준 알고리즘 16235번

https://www.acmicpc.net/problem/16235

16235번: 나무 재테크

---

16235번

N * N 크기의 땅에서 나무 재테크를 하자. (처음에 땅에는 양분의 양이 5로 모두 동일하다.)

나무는 아래와 같이 사계절을 보낸다.

• 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다. (당연히 자신이 있는 칸의 양분만 먹을 수 있다.)
  • 하나의 칸에 여러 개의 나무가 있을 경우 나이가 어린 나무부터 양분을 먹는다.
  • 만약 양분이 부족해 먹을 수 없다면 즉시 죽는다.
• 여름에는 봄에 죽은 나무가 양분으로 변하게 되는데, 죽은 나무의 나이를 2로 나눈 몫이 양분이 된다.
• 가을에는 나이가 5의 배수인 나무가 번식하는데 인접한 8개의 칸에 나이가 1인 나무가 생긴다.
• 겨울에는 땅에 양분을 추가하는데 각 칸에 추가되는 양분의 양은 2차원 배열 A로 입력으로 주어진다.

K년 후에 살아있는 나무의 개수를 구하여라.

 

입력으로 첫 줄에 땅의 크기 N, 나무의 개수 M, 시간 K가 들어온다.

그 다음 N개의 줄에 땅에 추가되는 양분의 양이 주어진다.

다음 M개의 줄에는 나무의 정보 x y z가 들어오는데 (x, y)는 나무의 위치이고 z는 나무의 나이이다.

 

출력으로 K년 후에 살아남은 나무의 수를 출력하면 된다.

---

문제 해결

각 4계절을 함수로 따로 구현하였다.

 

A는 겨울에 추가되는 양분의 양을 의미하고, Food는 먹을 수 있는 양분의 양을 나타낸다. 또한 Tree는 해당 위치에 있는 나무의 정보를 의미한다.

 

봄과 여름에 하는 일은 하나의 함수 SS 로 구현할 수 있다. 

Tree의 정보를 가지고 나무에 양분을 준다. 가장 어린 나무부터 양분을 먹다가 죽는 나무가 생기면 Food에 양분을 추가해준다. 

가을에 하는 일은 Autumn 함수가 해주는데 Tree의 정보를 보면서 나이가 5의 배수이면 인접 8칸에 나이가 1인 나무를 추가해주었다.

겨울에는 Food의 값에 A의 값을 더해주었다.

---

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static int N, M, K;
	static int[][] A, Food;
	static ArrayList<Integer>[][] Tree;
	static int[] di = { 1, -1, 0, 0, 1, 1, -1, -1 };
	static int[] dj = { 0, 0, 1, -1, 1, -1, 1, -1 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		A = new int[N][N];
		Food = new int[N][N];
		Tree = new ArrayList[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				A[i][j] = sc.nextInt();
				Food[i][j] = 5;
				Tree[i][j] = new ArrayList<>();
			}
		}

		for (int k = 0; k < M; k++) {
			// zero index로 맞추기 위해 -1
			int i = sc.nextInt() - 1;
			int j = sc.nextInt() - 1;
			int age = sc.nextInt();
			Tree[i][j].add(age);
		}
		// end input. init.

		int year = 0;
		while (year != K) {
			SS();
			Autumn();
			Winter();
			year++;
		}

		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cnt += Tree[i][j].size();
			}
		}
		System.out.println(cnt);
	}

	static void SS() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Tree[i][j].size() == 0)
					continue;
				int dead = 0;
				ArrayList<Integer> temp = new ArrayList<>();
				for (int p = 0; p < Tree[i][j].size(); p++) {
					int age = Tree[i][j].get(p);
					if (Food[i][j] >= age) {
						Food[i][j] -= age;
						temp.add(age + 1);
					} else {
						dead += age / 2;
					}
				}
				Tree[i][j] = temp;
				Food[i][j] += dead;
			}
		}
	}

	static void Autumn() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Tree[i][j].size() == 0)
					continue;
				for (int p = 0; p < Tree[i][j].size(); p++) {
					int age = Tree[i][j].get(p);
					if (age % 5 == 0) {
						for (int k = 0; k < 8; k++) {
							int ni = i + di[k];
							int nj = j + dj[k];
							if (ni < 0 || nj < 0 || ni >= N || nj >= N) {
								continue;
							}
							Tree[ni][nj].add(1);
						}
					}
				}
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (Tree[i][j].size() == 0)
					continue;
				Collections.sort(Tree[i][j]);
			}
		}
	}

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

}

---

결과

---

시간과 메모리를 좀 더 줄일 수 있을 것 같은데 아직 생각이 나지 않아서 고치지 못했다..