Node.js) 백준 1005번: ACM Craft

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

1005번: ACM Craft

 

골드 3단계 문제인데, Node로 풀면 골드3문제는  아닌 거 같다. 

다른 언어로는 그냥 위상정렬로 통과하는데,  Node에서는 시간초과 때문에  dfs + dp 로 푼 사람이 많았다. 

 

나도 처음에는 단순히 위상정렬로 풀었는데 시간초과가 나서 입력방식을 fs 에서 readline으로 바꾸고,  input값을 Array말고 Queue에 담아서 푸니까 통과했다. 

 

다들 dp로 열심히 풀었는데, 나만 입력모듈 바꿔서 그냥 위상정렬로 풀었다고 생각하니 통과하고도 좀 찝찝하다; 

 

class Node {
	constructor(item) {
		this.item = item;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.head = null;
		this.tail = null;
		this.length = 0;
	}

	push(item) {
		const node = new Node(item);
		if (this.head == null) {
			this.head = node;
		} else {
			this.tail.next = node;
		}

		this.tail = node;
		this.length += 1;
	}

	pop() {
		const popItem = this.head;
		this.head = this.head.next;
		this.length -= 1;
		return popItem.item;
	}
}
const readline = require('readline');

const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

let input = new Queue();

rl.on('line', function (line) {
	input.push(line.split(' ').map(Number));
}).on('close', function () {
	const T = input.pop()[0];
	const answer = [];
	for (let t = 0; t < T; t++) {
		const [N, M] = input.pop();
		let degree = Array(N).fill(0);
		const adj = Array.from(Array(N), () => []);
		let result = Array(N).fill(0);
		let cost = input.pop();
		for (let i = 0; i < M; i++) {
			const [x, y] = input.pop().map((v) => v - 1);
			degree[y]++;
			adj[x].push(y);
		}
		const target = input.pop()[0] - 1;

		const q = new Queue();

		for (let i = 0; i < degree.length; i++) {
			if (degree[i] == 0) {
				q.push(i);
				result[i] = cost[i];
			}
		}

		while (q.length > 0) {
			const now = q.pop();
			if (now == target) {
				answer.push(result[target]);
				break;
			}

			for (let i = 0; i < adj[now].length; i++) {
				const next = adj[now][i];
				result[next] = Math.max(result[next], result[now] + cost[next]);
				degree[next]--;
				if (degree[next] == 0) q.push(next);
			}
		}
	}
	console.log(answer.join('\n'));
	process.exit();
});