백준 16235 : 나무 재테크

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

16235번: 나무 재테크

[ 문제풀이 ]

이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다. 특별한 알고리즘이 요구되는 문제는 아니지만 시간이 굉장히 타이트한 문제이기 때문에 자료구조 선택을 잘해야 할 것이다.

​나는 처음에 나이가 어린 나무부터 양분을 먹는다는 조건 때문에 우선순위 큐를 사용하여 구현했지만 우선순위 큐는 원소 하나를 뽑아낼 때마다 O(log N)의 시간이 걸리기 때문에 적합한 자료구조가 아니었다.

따라서 삽입, 삭제가 O(1)의 시간 복잡도를 가지는 연결 리스트를 사용하여 해결하였다.

​시간 초과를 제외하고선 특별히 주의해야 할 부분은 없는 것 같다. 다만, 나이가 5의 배수인 나무를 번식할 때 8방향으로 번식 후 자기는 죽는 것이 아니고 살아있다는 부분만 조심하면 될 것 같다.

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

public class Main {

	static int n, m, k;
	static int[][] map, A;
	static LinkedList<Tree> lives, deads;

	static int[][] dir = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};

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

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

		public int compareTo(Tree o) {
			return this.age - o.age;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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 + 1][n + 1];
		A = new int[n + 1][n + 1];
		for (int i = 1; i <= n; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; ++j) {
				A[i][j] = Integer.parseInt(st.nextToken());
				map[i][j] = 5;
			}
		}

		lives = new LinkedList<>();
		deads = new LinkedList<>();
		for (int i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int age = Integer.parseInt(st.nextToken());

			lives.offer(new Tree(y, x, age));
		}

		while (k-- > 0) {
			spring();
			summer();
			fall();
			winter();
		}

		bw.write(lives.size() + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void spring() {
		Collections.sort(lives); //살아있는 나무를 나이가 어린 순서로 정렬		
		
		int size = lives.size();

		for (int i = 0; i < size; ++i) {
			Tree t = lives.poll();

			//양분이 부족하다면 죽은 나무 리스트에 삽입
			if (map[t.y][t.x] < t.age) {
				deads.add(t);
				continue;
			}

			//땅의 양분을 감소시켜주고 나이를 1증가하여 살아있는 나무 리스트에 삽입
			map[t.y][t.x] -= t.age;
			t.age++;
			lives.offer(t);
		}
	}

	public static void summer() {
		//죽은 나무 리스트를 돌면서 땅에 양분 추가
		while (!deads.isEmpty()) {
			Tree t = deads.poll();
			map[t.y][t.x] += t.age / 2;
		}
	}

	public static void fall() {
		int size = lives.size();

		for (int i = 0; i < size; ++i) {
			Tree t = lives.poll();
			//번식하고 나서 사라지는 것이 아니기 때문에 살아있는 나무 리스트에 삽입
			lives.offer(t);
			
			//나이가 5의 배수가 아니라면
			if (t.age % 5 != 0) continue;
			
			//인접한 8방향을 돌면서 영역을 벗어나지 않으면 살아있는 나무 리스트에 삽입
			for (int d = 0; d < 8; ++d) {
				int ny = t.y + dir[d][0];
				int nx = t.x + dir[d][1];

				if (ny < 1 || nx < 1 || ny > n || nx > n) continue;
				lives.offer(new Tree(ny, nx, 1));
			}
		}
	}

	public static void winter() {
		//모든 map에 양분을 추가
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				map[i][j] += A[i][j];
			}
		}
	}
}