[16235] 나무 재테크

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

16235번: 나무 재테크

---

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

class Main {

	static int N, M, K, x, y, z;
	static int[][] A, map;
	static ArrayList<Tree> list = new ArrayList<Tree>();
	static ArrayList<Tree> live;
	static ArrayList<Tree> dead;
	static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { -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+1][N+1];
		map = new int[N+1][N+1];

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				A[i][j] = sc.nextInt();
				map[i][j] = 5;
			}
		}

		for (int i = 0; i < M; i++) {
			x = sc.nextInt();
			y = sc.nextInt();
			z = sc.nextInt();
			list.add(new Tree(x, y, z));
		}

		for(int i=0; i<K; i++) {
			live = new ArrayList<Tree>();
			dead = new ArrayList<Tree>();
			spring();
			summer();
			autumn();
			winter();
		}
		
		System.out.println(list.size());
	}
	

	// 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가한다.
	// 하나의 칸에는 여러개의 나무가 있을 수 있는데, 나이가 어린 나무부터 양분을 먹는다.
	// 양분이 부족해 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 즉시 죽는다.
	public static void spring() {
		
		// 나이가 어린 나무부터 양분을 먹는다.
		Collections.sort(list);
		
		for (int i = 0; i < list.size(); i++) {
			Tree t = list.get(i);
			// 양분이 부족해서 자신의 나이만큼 양분을 먹을 수 없는 나무는 양분을 먹지 못하고 죽는다.
			if (map[t.row][t.col] < t.age) {
				dead.add(new Tree(t.row, t.col, t.age));
			} else {
				// 양분을 먹을 수 있으면 자신의 나이만큼 양분을 먹고, 나이가 1증가한다.
				map[t.row][t.col] -= t.age;
				live.add(new Tree(t.row, t.col, t.age+1));
			}
		}
		list.clear();
		list = new ArrayList<Tree>(live);
	}

	// 여름에는 봄에 죽은 나무가 양분으로 변하게 된다.
	// 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 추가된다. 소수점 아래는 버린다.
	public static void summer() {
		for (int i = 0; i < dead.size(); i++) {
			Tree t = dead.get(i);
			map[t.row][t.col] += (t.age / 2);
		}
	}

	// 가을에는 나무가 번식한다.
	// 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8칸에 나이가 1인 나무가 생긴다.
	public static void autumn() {
		for (int i = 0; i < live.size(); i++) {
			Tree t = live.get(i);
			if (t.age % 5 == 0) {
				// 인접한 8칸에 나이가 1인 나무 퍼뜨리기.
				for(int j=0; j<8; j++) {
					int nx = t.row + dir[j][0];
					int ny = t.col + dir[j][1];
					
					if(isInside(nx, ny)) list.add(new Tree(nx, ny, 1));
				}
			}
		}
	}
	
	// 겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가한다.
	public static void winter() {
		for(int i=1; i<=N; i++) 
			for(int j=1; j<=N; j++) 
				map[i][j] += A[i][j];
	}

	public static boolean isInside(int x, int y) {
		if (x >= 1 && x <= N && y >= 1 && y <= N) return true;
		else return false;
	}
}

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 t) {
		return this.age-t.age;
	}
}

---

전형적인 시뮬레이션 문제로 봄 ~ 겨울 순서대로 주어진 연산을 차례대로 코딩하는 문제입니다. 저는 이 문제에서 나무를 클래스로 선언하여 봄에 [ 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 먹는다 ] 라는 조건을 Comparable 을 사용하여 정렬하였는데, 비교조건을 if(this.age > t.age) return 1 else return -1 을 사용하면 런타임 에러가 발생하고 그냥 바로 return this.age-t.age 를 하면 정답이라고 나오는 부분이 이해가 안갔습니다. 지금도 왜 런타임 에러가 발생하는지 이해가 안되는데 다음에 알게 되면 다시 정리해야 될 것 같습니다.

그리고 처음에 봄에서 연산을 수행했을 때 ArrayList live 와 dead 를 선언하여 따로따로 살아있는 나무와 죽어있는 나무를 넣어주지 않고 Tree 클래스에 boolean 타입으로 살아있는지 죽어있는지 표시하는 변수를 두었었는데, 그렇게하면 매 연산마다 모든 나무에서 나무가 죽었는지 살았는지 봐야하기 때문에 시간초과가 발생했습니다. 그래서 live와 dead라는 ArrayList를 선언하여 따로 넣어주고 dead 에 있는 나무로만 여름에 양분을 추가하니 시간초과가 사라지는 부분을 블로그에서 힌트로 얻어서 풀었습니다.

[ 문제 풀이 ]

1. K 년 동안 봄~겨울 까지 연산을 수행하고 매번 live 와 dead 를 초기화 시켜줍니다.

2. 봄(spring) 에서는 조건이 한칸에 여러개의 나무가 있을 수 있기 때문에 처음에 먼저 나이가 어린나무부터 정렬을 해주고 양분이 부족해서 먹지못하는 죽은 나무는 dead에, 살아있는 나무는 live에 넣습니다. 그리고 마지막에 처음 입력받은 나무들이 들어있는 list를 clear해주고 살아있는 나무들이 들어있는 live를 list에 넣습니다.

3. 여름(summer) 에서는 죽은 나무가 양분으로 변하는 연산이므로 dead 에 있는 나무들만 양분으로 추가시킵니다.

4. 가을(autumn) 에서는 나무가 번식하므로 live에 있는 나무들만 연산을 수행하고 인접한 8칸에 나무를 번식시킵니다.

5. 겨울(winter) 에서는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가하므로 모든 2차원 배열 map 에 주어진 양분만큼 더해줍니다.