[백준][위상정렬] 2252 줄세우기 NodeJs 구현

     

목차

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

문제

 

문제 구현 방향

아래 위상 정렬을 참고해서 다시 구현했다.

https://charles098.tistory.com/12

[C++] 위상 정렬(Topology Sort)

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

class Queue {
  constructor() {
    this.store = new Map();
    this.front = 0;
    this.end = 0;
  }
  front() {
    return this.store.get(this.front);
  }
  size() {
    return this.store.size;
  }
  add(node) {
    this.store.set(this.end, node);
    this.end++;
  }
  pop() {
    if (this.size() === 0) return undefined;
    const item = this.store.get(this.front);
    this.store.delete(this.front);
    this.front++;
    if (this.size() === 0) {
      this.front = 0;
      this.end = 0;
    }
    return item;
  }
}
let v = Array.from({ length: 320001 }, () => []);
let ds = Array(320001).fill(0);
let queue = new Queue();
let ans = [];
function sorting() {
  for (let i = 1; i <= N; i++) {
    if (ds[i] === 0) queue.add(i);
  }
  while (queue.size()) {
    let q = queue.pop();
    ans.push(q);
    for (let i = 0; i < v[q].length; i++) {
      let a = v[q][i];
      ds[a]--;
      if (ds[a] === 0) {
        queue.add(a);
      }
    }
  }
}

let [N, M] = input[0].trim().split(" ").map(Number);
input.splice(0, 1);
for (let i = 0; i < input.length; i++) {
  let [A, B] = input[i].trim().split(" ").map(Number);
  v[A].push(B);
  ds[B]++;
}
sorting();
for (let i = 0; i < ans.length; i++) {
  process.stdout.write(`${String(ans[i])} `);
}