[백준1516_자바스크립트(javascript)] - 게임 개발

🔴 문제

게임 개발

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const [n] = inputs[0];
const graph = Array.from({ length: n + 1 }, () => []);
const indegree = Array(n + 1).fill(0);
const costs = Array(n + 1).fill(0);
const dp = Array(n + 1).fill(0);

for (let i = 1; i <= n; i++) {
  dp[i] = costs[i] = inputs[i].shift();

  inputs[i].pop();

  for (const num of inputs[i]) {
    graph[num].push(i);
    indegree[i] += 1;
  }
}

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

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

  for (const next of graph[node]) {
    dp[next] = Math.max(dp[node] + costs[next], dp[next]);

    indegree[next] -= 1;

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

for (let i = 1; i <= n; i++) {
  console.log(dp[i]);
}

🟢 풀이

⏰ 소요한 시간 : -

이 문제는 DP + 위상정렬 문제다.
건물을 짓을때 순서가 정해져 있다는 점에서 위상정렬을 사용해 풀어야 함을 알 수 있다. 또한 누적합을 사용해야 하는 점에서 DP를 사용할 수 있다.

따라서 DP를 다음과 같이 정의했다.

// n번 건물을 지을 때의 비용(시간)
// = n번 건물을 짓기 전에 먼저 지어야 하는 건물 + 자기 건물을 짓는 시간
// 위의 dp가 수행되려면 이전에 지어야 할 건물을 먼저 지어줘야함
// 즉 이전단계(위상정렬) 순서대로 dp를 채워야 함
dp[n] = Math.max(dp[이전단계]) + cost[n]

입력을 순회하면서 그래프에 현재 그래프와 이어진 다른 그래프 정보와 진입차수를 기록한다.

그 후 진입차수가 0인 노드를 큐에 넣어준 뒤, 큐가 빌때까지 위상정렬을 수행하면 된다.
dp는 위에서 정의한대로 업데이트를 할 텐데, 이전단계인 dp[node] + costs[next]와 dp[next]중에 더 큰 값을 골라야 한다.
왜냐하면 이 문제에서 주어지는 정점간 연결 정보는 직접 연결된 정점 정보만 주어지는 것이 아니다.
예를들어 4번 건물을 짓기 전에 1번 건물, 3번 건물을 지어야 하지만 그래프 상으로는 1번 노드에 2, 3, 4번 건물이 모두 이어진 것 처럼 되어있다. 4번 건물은 사실 3번 건물과 연결되어 있지만 1번과 연결된 것처럼 판단되기 때문에 이미 방문했을 수도 있기 때문이다.

위상정렬을 수행한뒤 dp를 통해 정답을 출력해주면 된다.

🔵 Ref