백준 16235 - 나무 재테크 JAVA

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

16235번: 나무 재테크

 

구현하면 되는 문제

1시간 조금 넘게 풀었다.

살아있는 나무와 죽는 나무 리스트들을 제대로 초기화를 하지 않아서 

자꾸만 시간 초과가 나와 골치 먹었던 문제다.

 

나이가 어린 나무부터 양분을 받으므로

Tree class를 정의할 때,  Comparable <> interface를 implements 받아주는 것만 주의해주면 된다.

 

리스트를 복사할 때, addAll() 메서드를 사용하면 되지만 또한

list = new ArrayList<>(newList) 형식으로 가져갈 수도 있다.

 

메서드를 잘 분리하고 전역 변수를 초기화하는 것에 더 주의하며 문제를 풀도록 하자!

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Tree implements Comparable<Tree> {
	int x;
	int y;
	int age;

	Tree(int x, int y, int age) {
		this.x = x;
		this.y = y;
		this.age = age;
	}

	// 나이 오름차순으로 정렬
	@Override
	public int compareTo(Tree t) {
		return this.age - t.age;
	}
}

public class 백준_나무제테크_16235 {
	static int N, M, K;
	static int[][] A;
	static int[][] map;
	static ArrayList<Tree> trees = new ArrayList<>();
	static ArrayList<Tree> liveTrees;
	static ArrayList<Tree> deadTrees;
	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 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());

		map = new int[N][N];
		A = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = 5;
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			trees.add(new Tree(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1,
					Integer.parseInt(st.nextToken())));

		}

		while (K > 0) {
			// 구분 초기화
			liveTrees = new ArrayList<>();
			deadTrees = new ArrayList<>();
			// 정렬
			Collections.sort(trees);
			spring();
			summer();
			fall();
			winter();
			K--;
		}
		System.out.println(trees.size());
	}

	// 봄
	static void spring() {
		for (int i = 0; i < trees.size(); i++) {
			Tree t = trees.get(i);
			if (t.age > map[t.x][t.y]) {
				deadTrees.add(t);
			} else {
				map[t.x][t.y] -= t.age;
				t.age += 1;
				liveTrees.add(t);
			}
		}
		// 나무 리스트 리셋 후 살아있는 나무로 초기화
		trees.clear();
		trees.addAll(liveTrees);
	}

	// 여름
	static void summer() {
		for (int i = 0; i < deadTrees.size(); i++) {
			Tree t = deadTrees.get(i);
			map[t.x][t.y] += t.age / 2;
		}
	}

	// 가을
	static void fall() {
		for (int i = 0; i < trees.size(); i++) {
			Tree t = trees.get(i);
			if (t.age % 5 == 0) {
				for (int j = 0; j < 8; j++) {
					int px = t.x + dx[j];
					int py = t.y + dy[j];
					if (0 <= px && px < N && 0 <= py && py < N) {
						trees.add(new Tree(px, py, 1));
					}
				}
			}
		}
	}

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

	static void print() {
		for (int i = 0; i < trees.size(); i++) {
			System.out.println(trees.get(i).x + " " + trees.get(i).y + " " + trees.get(i).age);
		}
	}

	static void printMap() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}
}