[백준2623_자바스크립트(javascript)] - 음악프로그램

🔴 문제

음악프로그램

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n, m], ...inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const graph = Array.from({ length: n + 1 }, () => []);
const inDegree = Array(n + 1).fill(0);
const q = [];

for (const input of inputs) {
  for (let i = 1; i < input.length - 1; i++) {
    const s = input[i];
    const e = input[i + 1];

    graph[s].push(e);
    inDegree[e] += 1;
  }
}

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

const ans = [];
while (q.length) {
  const current = q.shift();

  ans.push(current);

  for (const next of graph[current]) {
    inDegree[next] -= 1;

    if (inDegree[next] === 0) q.push(next);
  }
}

if (ans.length < n) console.log(0);
else console.log(ans.join('\n').trim());

🟢 풀이

⏰ 소요한 시간 : -

위상 정렬의 기본 유형이다.
문제에서 두번째줄부터 n번째 줄까지 주어지는 노드의 순서만 잘 체크해주면 된다. 각 줄의 1번째 자리부터 끝까지 시작 - 끝 노드 순서에 맞게 graph의 연결정보를 확인하고, 진입차수를 세어준다.

진입차수가 0인 노드를 큐에 넣고 큐가 빌 때까지 지금 탐색중인 노드와 연결된 간선을 제거하며 진입차수를 갱신하고, 새롭게 진입차수가 0이되면 큐에 넣어준다.

이후 정답을 출력해주면 된다.
올바른 순서라면, ans에 모든 노드가 들어가 n의 길이가 된다. 이 경우에 정답을 출력형태에 맞게 출력하고, ans의 길이가 n보다 작은 경우는 0을 출력해주면 된다.

🔵 Ref