백준 GOLD 3(게임 개발) - #1516

사용 언어 : javascript
해결 날짜 : 2023-05-25
해결 방법 :
- dp와 graph를 활용해 문제 해결
  - 건물 정보를 돌며 dp 초기화 및 graph 연결
    - 이 때 한 정점에 들어오는 간선의 수도 저장
  - 1부터 N까지 정점 중 들어오는 간선의 수가 0인 정점을 q에 삽입
  - q가 비어있지 않은 동안
    - graph의 from 방문 처리(to 정점에 들어오는 간선의 수 -= 1)
    - to 정점에 들어오는 간선의 수가 0일 때 q에 삽입
    - dp 값 업데이트
회고 :
- x

코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim();

solution(input);

function solution(props) {
  props = props.split('\n');
  const N = +props.shift();
  const buildings = props.map((e) =>
    e
      .replace(' -1', '')
      .split(' ')
      .map((v) => +v),
  );

  const graph = Array.from({ length: N + 1 }, () => []);
  const dp = Array.from({ length: N + 1 }, () => 0);
  const indegreeNum = Array.from({ length: N + 1 }, () => 0);

  buildings.forEach((building, i) => {
    const to = i + 1;
    dp[to] = building[0];

    building.slice(1).forEach((from) => {
      graph[from].push(to);
      indegreeNum[to] += 1;
    });
  });

  const q = [];

  for (let i = 1; i <= N; i++) {
    if (indegreeNum[i] === 0) {
      q.push(i);
    }
  }

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

    graph[from].forEach((to) => {
      if (--indegreeNum[to] === 0) {
        q.push(to);
      }

      dp[to] = Math.max(dp[to], dp[from] + buildings[to - 1][0]);
    });
  }

  dp.slice(1).forEach((v) => console.log(v));
}

출처: 백준