[백준][위상정렬] 3665 최종순위 NodeJs 구현

목차

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

문제

 

 

 

문제 구현 방향

위상 정렬을 위한 전처리가 생각하기 쉽지 않았다..

결국에 등수별로는 위상이 정해진 것이므로 순서대로 다 연결해준 뒤에 입력으로 주어진 것들만 순서를 바꾸어 주면 된다.

 

 

 

 

판별 시 조건

큐에서 제거하고 모은 출력값이 그 개수에 도달하지 않으면 impossible을 출력하고 큐의 개수가 2개 이상될 때 ?를 출력해주면 된다.

 

 

 

 

코드 구현

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

class queue {
  constructor() {
    this.store = new Map();
    this.front = 0;
    this.rear = 0;
  }
  size() {
    return this.store.size;
  }
  push(node) {
    this.store.set(this.rear, node);
    this.rear++;
  }
  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.rear = 0;
    }
    return item;
  }
}
function print(ans) {
  for (let i = 0; i < ans.length; i++) {
    process.stdout.write(`${String(ans[i])} `);
  }
  console.log();
}
function dsSearching(ds, v, t) {
  let ans = [];
  let q = new queue();
  for (let i = 1; i <= t; i++) {
    if (ds[i] === 0) {
      q.push(i);
    }
  }


  while (q.size()) {
    if (q.size() >= 2) {
      console.log("?");
      return;
    }
    let f = q.pop();
    ans.push(f);
    for (let i = 0; i < v[f].length; i++) {
      let t = v[f][i];
      ds[t]--;
      if (ds[t] === 0) {
        q.push(t);
      }
    }
  }
  if (ans.length !== t) {
    console.log("IMPOSSIBLE");
    return;
  }
  print(ans);
}

let T = +input[0];
input.splice(0, 1);
for (let i = 0; i < T; i++) {
  input.splice(0, 1);
  let v = Array.from({ length: 503 }, () => []);
  let ar = input[0].trim().split(" ").map(Number);
  let ds = Array(503).fill(0);
  for (let j = 0; j < ar.length - 1; j++) {
    for (let t = j + 1; t < ar.length; t++) {
      v[ar[j]].push(ar[t]);
      ds[ar[t]]++;
    }
  }
  input.splice(0, 1);
  let u = +input[0];
  input.splice(0, 1);
  for (let p = 0; p < u; p++) {
    let [a, b] = input[p].trim().split(" ").map(Number);
    let l;
    if ((l = v[a].indexOf(b)) !== -1) {
      v[a].splice(l, 1);
      ds[b]--;
      ds[a]++;
      v[b].push(a);
    } else {
      l = v[b].indexOf(a);

      v[b].splice(l, 1);
      ds[a]--;
      ds[b]++;
      v[a].push(b);
    }
  }

  input.splice(0, u);
  dsSearching(ds, v, ar.length);
}