백준 - 나무 재태크

문제 설명

주어진 조건에 따라 시물레이션

주의사항 : 시간 초과

나무의 위치를 2차원 배열에 담아 돌리면 TLE가 발생함.

백억 정도 나오기 때문이다.

핵심은 순회를 최대한 줄이는 것이다.

hint : 배열 각 칸이 아닌 나무만 보자

풀이

static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	static int n, m, k;
	static int[][] land; // 땅에 양분
	static int a[][]; // S2D2가 땅에 줄 양분들
	static int dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int dx[] = {0, 1, 1, 1, 0, -1, -1, -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 boolean isDead(int landVal) {
			return landVal < age;
		}

		public boolean isBreeding() {
			return this.age % 5 == 0;
		}

		public Tree getGrowTree() {
			return new Tree(this.y, this.x, this.age + 1);
		}

		public Tree copy() {
			return new Tree(this.y, this.x, this.age);
		}

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

	}

	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(reader.readLine());

		// n개의 땅.
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());

		land = new int[n][n];
		// 처음 땅의 기본 양분 설정
		for (int i = 0; i < n; i++) {
			Arrays.fill(land[i], 5);
		}

		// 기계가 양분을 줄 양 설정
		a = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < n; j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		PriorityQueue<Tree> trees = new PriorityQueue<>();

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(reader.readLine());

			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int age = Integer.parseInt(st.nextToken());

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

		while (k-- > 0) {
			// 봄: 자신의 나이만큼 양분을 먹는다, 못먹으면 죽는다.

			LinkedList<Tree> deads = new LinkedList<>();
			PriorityQueue<Tree> lives = new PriorityQueue<>();
			LinkedList<Tree> breedings = new LinkedList<>();
			while (!trees.isEmpty()) {
				Tree cur = trees.poll();

				if (cur.isDead(land[cur.y][cur.x])) {
					deads.offer(cur.copy());
				} else {
					land[cur.y][cur.x] -= cur.age;
					Tree newTree = cur.getGrowTree();

					if (newTree.isBreeding()) {
						breedings.offer(newTree);
					}

					lives.offer(newTree);
				}
			}

			// 여름: 죽은 나무가 양분이 된다.
			while (!deads.isEmpty()) {
				Tree dead = deads.poll();

				land[dead.y][dead.x] += dead.age / 2;
			}

			// 가을: 번식
			while (!breedings.isEmpty()) {
				Tree cur = breedings.poll();

				for (int i = 0; i < 8; i++) {
					int ny = dy[i] + cur.y;
					int nx = dx[i] + cur.x;

					if (isOutOfIndex(ny, nx))
						continue;

					lives.add(new Tree(ny, nx, 1));
				}
			}

			trees = lives;

			// 겨울: 양분 충전
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					land[i][j] += a[i][j];
				}
			}
		}

		System.out.println(trees.size());
	}

	public static boolean isOutOfIndex(int ny, int nx) {
		return ny < 0 || nx < 0 || ny >= n || nx >= n;
	}