[boj] 2252. 줄 세우기 (node.js)

요약

BOJ 2252 줄 세우기

• 입력: N명의 학생들의 키를 1:1로 비교한 M개의 결과가 주어진다.
• 출력: 키 순서대로 출력하라.
• 답이 여러 가지일 수 있다.

풀이

1. 문제에서 주어진 두 명씩 비교한 데이터를 인접 리스트 형태로 변환한다.
2. 인접 리스트의 데이터와 각 노드별 in-degree의 개수를 활용해 위상정렬한다.
3. 결과를 출력한다.

내 풀이

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

let cnt = 0;
const input = () => stdin[cnt++].split(" ").map(Number);

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  let [N, M] = input();
  let linkedList = new Array(N + 1);
  let degree = new Array(N + 1).fill(0);

  while (M--) {
    arr = input();
    degree[arr[1]]++;
    !linkedList[arr[0]]
      ? (linkedList[arr[0]] = [arr[1]])
      : linkedList[arr[0]].push(arr[1]);
  }

  let queue = [];
  degree.forEach((deg, idx) => {
    if (idx == 0) return;
    if (deg == 0) queue.push(idx);
  });

  let elem,
    result = [];
  while (queue.length > 0) {
    elem = queue.shift();
    result.push(elem);
    if (!linkedList[elem]) continue;
    linkedList[elem].forEach((item) => {
      degree[item]--;
      if (degree[item] == 0) queue.push(item);
    });
  }
  console.log(result.join(" "));
  process.exit();
});

• 인접 리스트에 저장해둔 노드간 연결 정보를 활용해 in-degree를 while 문 내에서 매번 갱신한다.
• in-degree == 0 이 되는 순간에만 답이 나올 수 있으므로 forEach 문 내부에서 degree[item]-- 후에 이어지는 if 문을 통해 queue.push를 수행할 수 있다.