엉금엉금

풀이 

문제는 직접 보고 오신 경우가 많을 것 같아서 제 풀이 먼저 올렸습니다.

const fs = require('fs');
const input = fs
  .readFileSync(__dirname + '/input.txt')
  .toString()
  .split('\n');

// 테스트 횟수
const T = +input[0];
let index = 1;

for (let t = 1; t <= T; t++) {
// 입력값 n은 건물 개수, k는 간선의 수
  const [n, k] = input[index].split(' ').map(Number);
  // 각각의 건물마다 건설 시간
  const timeArr = input[index + 1].split(' ').map(Number);
  // 입력값에서 간선의 인덱스로 이동
  index += 2;
  
  // 간선들을 그래프에 담기 위해서 (인덱스와 건물 번호가 일치하도록 n+1)
  const graph = Array(n + 1)
    .fill()
    .map(() => []);
   
  // 그래프에 간선 정보 담기
  for (let i = 0; i < k; i++) {
    const [start, end] = input[index + i].split(' ').map(Number);
    graph[end].push(start);
  }

  // 총 건설 시간의 초기값은 각각의 건물 시간으로 줌
  const minBuild = [0, ...timeArr];
  
  // 간선 지나치기
  index += k;
  // 완성 시켜야 하는 건물
  const target = input[index++];
  //총 건설 시간 배열을 활용하여 목표 건물의 총 건설 시간 구함
  console.log(countTotal(target));

// 재귀함수를 통해서 경로를 찾음, 이때 모든 건물의 건설 시간을 구하는게 아니라
// 목표 건물의 하위 건물들만 구해줌
  function countTotal(number) {
   //반복문을 통해서 목표 건물에 선행 건물이 있다면 해당 건물의 총 건설 시간 먼저 구함
    while (true) {
    // 선행 건물이 없다면 건설시간 반환
      if (graph[number].length === 0) {
        return minBuild[number];
      }
      // 선행 대상이 있다면, graph에서 해당 노드를 추출하고 총 건설시간을 구함
      const subTarget = graph[number].pop();
      // 총 건설 시간은 기존에 있는 값과 비교하여서 더 긴 경우에만 수정
      minBuild[number] = Math.max(
        minBuild[number],
        countTotal(subTarget) + timeArr[number - 1]
      );
    }
  }
}

문제 설명

문제 링크 및 출처 : https://www.acmicpc.net/problem/1005

풀이 배경

결국 목표 건물의 건설을 알기 위해선 선행 건물의 건설시간을 파악해야 한다.

이때 선행의 선행 건물이 존재할 수 있다.

따라서 재귀함수를 이용해서 문제를 해결하기로 결정

즉 , 다이나믹 프로그래밍과 dfs를 이용해서 문제를 풀었다.

따라서 그래프에 선행 건물 정보를 담아 놓고, 선행 건물이 있다면 선행 건물의 총 건설 시간 +  목표 건물의 건설 시간을 더해서 총 건설 시간을 구하는 방식으로 풀었다.

다른 풀이

보통 위상 정렬을 이용해서 해당 문제를 푸는 경우를 많이 봤다. 

선행 건물의 수가 적은 순으로 큐나 스택에 정보를 담아서 구하는 방법인데 아래 블로그에서 위상정렬을 이용한 풀이 방법 

을 설명해준다.

https://velog.io/@mk0504/%EB%B0%B1%EC%A4%80-1005%EB%B2%88-ACM-Craft-JavaScript