나무 재테크

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 우선순위 큐 구현
class MinHeap {
	constructor() {
		this.bucket = [null];
	}

	enqueue(item) {
		let index = this.bucket.length;

		while (index !== 1 && item < this.bucket[parseInt(index / 2)]) {
			this.bucket[index] = this.bucket[parseInt(index / 2)];
			index = parseInt(index / 2);
		}

		this.bucket[index] = item;
	}

	dequeue() {
		if (this.isEmpty()) return;

		let parentIdx = 1;
		let childIdx = 2;
		const item = this.bucket[1];
		const lastItem = this.bucket.pop();

		while (childIdx < this.bucket.length) {
			if (
				childIdx + 1 < this.bucket.length &&
				this.bucket[childIdx] > this.bucket[childIdx + 1]
			)
				childIdx += 1;

			if (lastItem <= this.bucket[childIdx]) break;

			this.bucket[parentIdx] = this.bucket[childIdx];

			parentIdx = childIdx;
			childIdx *= 2;
		}

		if (!this.isEmpty()) this.bucket[parentIdx] = lastItem;

		return item;
	}

	isEmpty() {
		return this.bucket.length === 1;
	}

	size() {
		return this.bucket.length - 1;
	}
}

// 봄
const spring = (n, grid) => {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			let [food, ageMinHeap, nextMinHeap] = grid[i][j];
			if (food === 0 || ageMinHeap.isEmpty()) continue;

			while (!ageMinHeap.isEmpty()) {
				const age = ageMinHeap.dequeue();

				// 나이가 양분의 양보다 크다면, 종료
				if (food < age) {
					ageMinHeap.enqueue(age);
					break;
				}

				// 나이가 양분의 양보다 작다면, 2 번 우선순위 큐에 "나이 + 1" 값 추가
				food -= age;
				nextMinHeap.enqueue(age + 1);
			}

			// 양분의 양 갱신
			grid[i][j][0] = food;
		}
	}
};

// 여름
const summer = (n, grid) => {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			let [food, ageMinHeap, nextHeap] = grid[i][j];

			// 1 번 우선순위 큐에서
			while (!ageMinHeap.isEmpty()) {
				const age = ageMinHeap.dequeue();

				// 나이 / 2 후 소수점 이하의 값을 버린 값을 양분에 추가
				food += parseInt(age / 2);
			}

			// 2 번 우선순위 큐에 있는 원소 1 번 우선순위 큐로 전달 (참조만 변경)
			grid[i][j][0] = food;
			grid[i][j][1] = nextHeap;
			grid[i][j][2] = new MinHeap();
		}
	}
};

// 총 8 가지 방향
const dir = [
	[-1, -1],
	[-1, 0],
	[-1, 1],
	[0, -1],
	[0, 1],
	[1, -1],
	[1, 0],
	[1, 1],
];

// 불가능한 칸인지 검사하는 함수
const isPossibleRoute = (n, x, y) => 0 <= x && x < n && 0 <= y && y < n;

// 가을
const autumn = (n, grid) => {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			const [food, ageMinHeap, nextMinHeap] = grid[i][j];

			if (ageMinHeap.isEmpty()) continue;

			// 1 번 우선순위 큐에서
			while (!ageMinHeap.isEmpty()) {
				// 2 번 우선순위 큐로 이동시키며,
				const age = ageMinHeap.dequeue();
				nextMinHeap.enqueue(age);

				// 나무의 나이가 5 의 배수라면 총 8 개의 칸에 나이가 1 인 나무 생성
				if (age % 5 === 0) {
					for (let k = 0; k < 8; k++) {
						const [nx, ny] = [i + dir[k][0], j + dir[k][1]];
						if (!isPossibleRoute(n, nx, ny)) continue;

						// 나이가 1 인 나무는 각 칸의 2 번 우선순위 큐에 넣기
						grid[nx][ny][2].enqueue(1);
					}
				}
			}
		}
	}

	// 2 번 우선순위 큐에 있는 나무 모두 1 번 우선순위 큐로 이동 (참조만 변경)
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			grid[i][j][1] = grid[i][j][2];
			grid[i][j][2] = new MinHeap();
		}
	}
};

// 겨울
const winter = (n, foodArr, grid) => {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			// 양분 추가
			grid[i][j][0] += foodArr[i][j];
		}
	}
};

const solution = (input) => {
	let [n, m, k] = input[0].split(" ").map(Number);
	const foodArr = input.slice(1, n + 1).map((v) => v.split(" ").map(Number));

	// N x N 크기의 땅 생성
	const grid = Array.from({length: n}, () => Array.from({length: n}, () => []));
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			grid[i][j].push(5);
			grid[i][j].push(new MinHeap());
			grid[i][j].push(new MinHeap());
		}
	}

	// 나무 정보 입력
	for (let i = n + 1; i < n + 1 + m; i++) {
		const [r, c, age] = input[i].split(" ").map(Number);
		const ageMinHeap = grid[r - 1][c - 1][1];

		ageMinHeap.enqueue(age);
	}

	// k 번만큼 봄, 여름, 가을, 겨울 로직 적용
	while (k-- > 0) {
		spring(n, grid);
		summer(n, grid);
		autumn(n, grid);
		winter(n, foodArr, grid);
	}

	// 살아남은 나무의 개수 세기
	let ans = 0;
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			const ageMinHeap = grid[i][j][1];

			ans += ageMinHeap.size();
		}
	}

	return ans;
};

console.log(solution(input));