[백준1005_자바스크립트(javascript)] - ACM Craft

🔴 문제

ACM Craft

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');

let idx = 0;
const T = Number(inputs[idx++]);

for (let _ = 0; _ < T; _++) {
  const [n, k] = inputs[idx++].split(' ').map(Number);
  const costs = [0, ...inputs[idx++].split(' ').map(Number)];
  const graph = Array.from({ length: n + 1 }, () => []);
  const inDegree = Array(n + 1).fill(0);

  for (let i = 0; i < k; i++) {
    const [x, y] = inputs[idx++].split(' ').map(Number);

    graph[x].push(y);
    inDegree[y] += 1;
  }

  const dp = Array(n + 1).fill(0);
  const q = [];

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

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

    for (const next of graph[current]) {
      inDegree[next] -= 1;
      dp[next] = Math.max(dp[current] + costs[next], dp[next]);

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

  const target = +inputs[idx++];
  console.log(dp[target]);
}

🟢 풀이

⏰ 소요한 시간 : -

위상정렬은 진입차수가 0인 노드를 선택해 큐에 넣고, 큐가 빌 때까지 큐에서 노드를 꺼내 노드와 연결된 간선을 제거한 뒤 진입차수가 0이 된 노드를 다시 큐에 넣어주는 과정을 반복하면 된다.
이 문제는 매 게임마다 건물을 짓는 순서가 주어진다. 또한 건설 순서는 모든 건물이 건설 가능하도록 주어진다는 조건이 있으므로 사이클이 없다는 의미이고, 위상정렬의 요구조건을 충족한다.

따라서 입력받은 연결정보를 그래프에 넣어주고, 진입차수를 체크해준다. 이 문제는 위상정렬을 수행하되, 각 노드로 들어오는 진입차수가 여러 개라면 건물을 건설하는데 가장 오래걸리는 시간을 채택해야 한다.
또한 이전 시간과 계속해서 비교하며 가장 오래걸리는 시간을 채택해야 하므로 해당 건물을 짓는데 소요되는 누적 시간을 체크할 dp 배열을 만들어준다.

정보 입력이 끝나면 진입차수 배열을 순회하며 진입차수가 0인 노드를 큐에 넣어주고, 이 노드는 진입차수가 0이므로 이전에 dp배열 값이 해당 건물을 짓는데 소요되는 시간이다.

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

그 후 큐가 빌 때까지 큐에 있는 노드를 하나 꺼내서 해당 노드와 연결된 간선을 제거해주는 과정을 가진다.
이 때 현재 건물을 짓는데 걸리는 시간과 다음 건물을 짓는데 걸리는 시간의 합과 다음 노드를 짓는데 걸리는 시간 중 최대값으로 dp배열을 갱신해준다.

마지막으로 백준이가 승리하기 위해 건설해야 할 건물의 번호를 dp배열에 인덱스로 넣어 출력하면 된다.

🔵 Ref