Node.js) 백준 2623번: 음악프로그램

 

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

2623번: 음악프로그램

예전에 학원 다닐 때, 선생님이 한 번 풀어보라고 했던 문제라서 기억이 난다. 

그 때는 진짜 어떻게 풀어야될지 감이 안 왔는데,

이제 꽤 쉽게 풀린다. 

 

감회가 새롭다. 

 

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;
        }
}

let input = require('fs')
        .readFileSync('./dev/stdin')
        .toString()
        .trim()
        .split('\n')
        .map((v) => v.split(' ').map(Number));

const [N, M] = input.shift();
let indegree = Array(N + 1).fill(0);
const adj = Array.from(Array(N + 1), () => []);
input.forEach((v) => {
        for (let i = 1; i < v.length - 1; i++) {
                indegree[v[i + 1]]++;
                adj[v[i]].push(v[i + 1]);
        }
});

const q = new Queue();

for (let i = 1; i < indegree.length; i++) {
        if (indegree[i] == 0) q.push(i);
}

const answer = [];
while (q.length > 0) {
        const node = q.pop();
        answer.push(node);

        for (let i = 0; i < adj[node].length; i++) {
                indegree[adj[node][i]]--;
                if (indegree[adj[node][i]] == 0) q.push(adj[node][i]);
        }
}

if (answer.length != N) console.log(0);
else console.log(answer.join('\n'));