[boj] 1005. ACM Craft (node.js)

문제 요약

[boj] 1005. ACM Craft (node.js)

• 각 노드는 건물 번호로, 건물 번호와 건설 시간이 주어진다.
• 연결된 노드의 정보들과 최종 노드가 주어질 때, 최종 노드까지 건설 소요시간 중 최소 소요시간을 출력
• 한 노드는 선행된 노드들의 건설이 모두 완료되어야만 시작 가능하며, 진입이 없는 노드는 동시 건설이 가능하다.

풀이

• 위상정렬을 통한 최종노드까지의 정렬 순서가 바로 최소 시간을 가질 수 있는 후보들이다. 즉 위상정렬 알고리즘을 구현하면 최소시간을 보장한다.
  • 알고리즘의 재료(배열): 각각 계속 노드를 넣고 뺄 queue, 문제에서 주어진 각 노드에서의 소요시간, 매번 갱신될 노드까지의 최소 시간, in-degree를 저장할 배열
• 반드시 앞선 노드가 완료되어야 다음 노드의 건설이 시작된다는 조건이 있으므로 위상정렬 알고리즘 내에서 results[elem] = Math.max(results[item] + time[elem], results[elem]); 을 통해 매번 특정 노드에 진입하는 간선을 확인할 때마다 max 값이 그 노드까지의 소요시간이 되도록 갱신한다.

내 풀이

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

let cnt = 0;
const input = () => stdin[cnt++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  const T = input();
  let result = [];
  for (let i = 0; i < T; i++) {
    // get input
    const [N, K] = input().split(" ").map(Number);
    let time = input().split(" ").map(Number);
    time.unshift(0);
    let arr = [];
    let degree = new Array(N + 1).fill(0);
    for (let i = 0; i < K; i++) {
      const elem = input().split(" ").map(Number);
      if (!arr[elem[0]]) arr[elem[0]] = [];
      arr[elem[0]].push(elem[1]);
      degree[elem[1]]++;
    }
    let W = input();

    // new queue
    let queue = [];
    let results = new Array(N + 1).fill(0);
    for (let i = 1; i <= N; i++) {
      if (degree[i] == 0) {
        queue.push(i);
        results[i] = time[i];
      }
    }

    // topological sort start
    while (queue.length) {
      const item = queue.shift();
      if (!arr[item]) continue;
      arr[item].forEach((elem) => {
        degree[elem]--;
        if (degree[elem] == 0) queue.push(elem);
        results[elem] = Math.max(results[item] + time[elem], results[elem]);
      });
    }
    result.push(results[W]);
  }
  console.log(result.join("\n"));
  process.exit();
});