[백준1766_자바스크립트(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 }, () => Array());
const indegree = Array(n + 1).fill(0);

for (const [a, b] of inputs) {
  graph[a].push(b);
  indegree[b] += 1;
}

const getNextNode = () => {
  for (let i = 1; i <= n; i++) {
    if (indegree[i] === 0) {
      indegree[i] -= 1;
      return i;
    }
  }
};

let ans = '';

for (let _ = 0; _ < n; _++) {
  const current = getNextNode();

  ans += current + ' ';

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

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

위상정렬 + 우선순위 큐 문제다.

처음에는 단순하게 위상정렬로 풀면 되겠다고 생각했는데 문제 조건 중 다음과 같은 조건이 있다.

가능하면 쉬운 문제부터 풀어야 한다.

위상정렬은 진입차수가 0이 된 노드가 큐에 들어가고, 그 큐의 요소를 차례대롵 탐색하는 문제다. 그런데 한 번의 탐색 때, 진입차수가 0이된 노드(문제)가 여러개라면, 그 문제들 중 가장 쉬운문제 즉 인덱스가 가장 작은 노드를 선택해야 한다. 그런데 큐에 들어갈 때 인덱스가 가장 작은 노드임을 보장할 방법이 없다.

그래서 우선순위 큐 개념도 도입해야 한다.

연결된 간선에 맞게 진입차수를 체크해준다.
그 후 일반 큐에서 값을 빼내는 대신, getNextNode 함수를 통해 인덱스가 가장작고, 진입차수가 0이 된 노드를 가져올 수 있도록 한다.
그 후 위상정렬과 동일하게 구현하면 정답을 구할 수 있다.

🔵 Ref

위상정렬