[백준2252_자바스크립트(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);

for (let i = 0; i < m; i++) {
  const [a, b] = inputs[i];

  graph[a].push(b);
  inDegree[b] += 1;
}

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

let ans = '';
while (q.length) {
  const current = q.shift();
  ans += current + ' ';

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

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

console.log(ans.trim());

🟢 풀이

⏰ 소요한 시간 : -

위상정렬의 문제 유형이다.
문제에서 일부 학생들의 비교정보만 주어지는데 해당 정보를 가지고 "키 순서"를 나열할 수 있다.
그렇기 때문에 입력받은 정보를 통해 그래프 연결정보와, 진입차수를 계산해준다.
그 후 반복문을 돌면서 진입차수가 0인 노드(학생 번호)를 큐에 집어넣어 큐가 빌때까지 위상정렬 로직을 수행한다.
큐의 맨 앞의 노드를 꺼내 해당 노드로부터 연결된 간선을 제거해주고, 새롭게 진입차수가 0이 된 노드를 큐에 넣어주면 된다.
이 때 큐에서 노드를 뽑아주는 순서가 학생들의 키 순서가 된다.

🔵 Ref