[BaekJoon] 16235 나무 제테크 (Java)

1.  문제 링크

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

2.  문제

요약

• N x N 크기의 땅을 상도가 가지고 있고, 각 칸은 (r, c)로 나타냅니다. r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수를 의미하며, r과 c는 1부터 시작합니다.
• 땅의 양분을 조사하는 로봇 S2D2는 1 x 1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해서 조사를 합니다.
• 가장 처음에 양분은 모든 칸에 5만큼 들어있습니다.
• 상도는 나무 제테크를 하기 위해 M개의 나무를 구매해 땅에 심는데, 1 x 1 크기의 칸에 여러 개의 나무가 심어져 있을 수도 있습니다.
• 나무는 사계절을 보내며 아래와 같은 과정을 반복합니다.
  • 봄에는 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가합니다. 각 나무는 해당 나무가 있는 1 x 1 크기의 칸에 있는 양분만 먹을 수 있고 하나의 칸에 여러 개의 나무가 있다면 나이가 어린 나무부터 양분을 먹습니다. 만약 땅에 양분이 부족하다면 양분을 먹을 수 없는 나무는 즉시 죽습니다.
  • 여름에는 봄에 죽은 나무가 죽은 나무마다 나이를 2로 나눈 값이 나무가 있던 칸에 양분으로 변합니다.
  • 가을에는 나무가 번식하는데, 번식하는 나무는 나이가 5의 배수이어야 하며, 인접한 8개의 칸에 나이가 1인 나무가 생깁니다. 상도의 땅을 벗어나는 칸에는 나무가 생기지 않습니다.
  • 겨울에는 S2D2가 땅을 돌아다니면서 땅에 양분을 추가합니다.(양분의 양 : A[r][c])
• K년이 지난 후, 상도의 땅에 살아있는 나무의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 10보다 작거나 같은 N, 1보다 크거나 같고 $N^2$보다 작거나 같은 M, 1보다 크거나 같고 1,000보다 작거나 같은 K가 주어지고 두 번째 줄부터 N개의 줄에는 A 배열의 값이 주어집니다. r번째 줄의 c번째 값은 A[r][c]입니다. 다음 M개의 줄에는 상도가 심은 나무의 정보를 나타내는 세 정수 x, y, z가 주어집니다. 이는 나무의 위치인 (x, y)와 해당 나무의 나이를 의미합니다.
• 출력: 첫 번째 줄에 K년이 지난 후 살아남은 나무의 수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, K;
	static LinkedList<Tree> trees;
	static Queue<Tree> dead;
	static int[][] A, nourishment;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		K = scanner.nextInt();
		trees = new LinkedList<>();
		dead = new LinkedList<>();
		A = new int[N][N];
		nourishment = new int[N][N];
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) {
				nourishment[row][col] = 5;
				A[row][col] = scanner.nextInt();
			}
		}
		for(int count = 0; count < M; count++) {
			int x = scanner.nextInt(), y = scanner.nextInt(), age = scanner.nextInt();
			trees.add(new Tree(x - 1, y - 1, age));
		}
	}
	
	static void solution() {
		Collections.sort(trees);
		for(int year = 1; year <= K; year++) {
			spring();
			summer();
			fall();
			winter();
		}
		System.out.println(trees.size());
	}
	
	static void spring() {
		LinkedList<Tree> temp = new LinkedList<>();
		for(Tree tree : trees) {
			if(tree.age <= nourishment[tree.x][tree.y]) {
				temp.add(new Tree(tree.x, tree.y, tree.age + 1));
				nourishment[tree.x][tree.y] -= tree.age; 
			} else {
				dead.offer(tree);
			}
		}
		trees = temp;
	}
	
	static void summer() {
		while(!dead.isEmpty()) {
			Tree tree = dead.poll();
			nourishment[tree.x][tree.y] += (tree.age / 2); 
		}
	}
	
	static void fall() {
		int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, 1, 1, 1, 0, -1, -1, -1};
		LinkedList<Tree> temp = new LinkedList<>();
		for(Tree tree : trees) {
			if(tree.age % 5 == 0) {
				for(int dir = 0; dir < 8; dir++) {
					int cx = tree.x + dx[dir], cy = tree.y + dy[dir];
					if(isInMap(cx, cy)) temp.add(new Tree(cx, cy, 1));
				}
			}
		}
		trees.addAll(0, temp);
	}
	
	static void winter() {
		for(int row = 0; row < N; row++) {
			for(int col = 0; col < N; col++) nourishment[row][col] += A[row][col];
		}
	}
	
	static boolean isInMap(int x, int y) {
		if(x >= 0 && x < N && y >= 0 && y < N) return true;
		return false;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Tree implements Comparable<Tree> {
		int x, y, age;
		public Tree(int x, int y, int age) {
			this.x = x;
			this.y = y;
			this.age = age;
		}
		public int compareTo(Tree t) {
			return age - t.age;
		}
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}