백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 1005 , ACM Craft [위상정렬, DP]

백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 1005 , ACM Craft [위상정렬, DP]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

 

문제 출처 🏠

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

 

 

 

 

문제풀이 소감 🧑‍💻

2252 번 문제는 위상정렬 표준 문제였다면, 이 문제는 + DP 활용도 들어간다.

정렬하는 결과값은 나오지 않는다고해서 위상정렬 문제라고 하기 뭐하다는 의견도 보였는데, 그래도 개념을 연습하기에는 좋은 문제 같다. 

 

다만, 자바스크립트로 이 문제를 풀려다보니 input 을 받는 과정에서 시간초과가 오히려 생겼음.

shift() 는 어지간하면 쓰지 말자...

 

 

 

요구사항 📋

T개의 테스트케이스.
N개의 건물과 K개의 건설순서 규칙.
각 건물당 건설에 걸리는 시간이 주어짐.
K개의 건설순서가 주어짐.
승리하기 위해 건설해야 할 건물의 번호가 주어짐.
해당 건물을 건설하는데 걸리는 최소시간을 구하시오.

 

 

주의 ❗

지을 건물 이전 순위 와 동일하면서 아직 건설해야할 건물들이 있다면 이전 건설들을 모두 마쳐야만, 해당 건물을 건설 할 수 있다.

ex) 2 -> 4, 3 -> 4 일 때, 4번 건물을 짓기 위해선 2번,3번 건물이 모두 건설완료 되어야함.

      2번, 3번은 동일한 건물짓기의 순서를 가졌기 때문.

 

 

가장 중요한 핵심은

 

이 문제는 승리하기 위해 건설할 건물로 이어져있는 간선중에서 가장 빨리 도착하는 것을 찾는 문제이다.

 

만약, 승리하기 위해 건설할 건물이 5번이고,

 

1-> 3 ->5

 

1->4->5 

 

1->2->8->5

 

라고 가정했을때, 확인할 값은

 

1-> 3 ->5

 

1->4->5 

 

 

이 두가지뿐이다.

 

1->2->8->5

 

경로는 총 3번의 간선을 거쳐야해, 위 두가지 경로보다 늦게 도착하게되므로 고려해야할 계산에서 제외가 된다는 것을 잊지말자.

 

이 이유때문에 rank 배열을 통해 우선순위를 체크해주는 것이다. 5번에 이미 도착했는데 후순위들을 고려할 필요가 없다.

 

승리하기 위해 지을 건물에 도착하는 모든 경로를 탐색하는 것이 아닌 제일 먼저 건설하면서 그 중 가장 긴 시간이 소요되는 값을 찾는 게 이 문제가 요구하는 해답이다.

 

 

 

 

 

해결 전략 📝

우선순위가 0인 노드가 루트 노드.
자식노드로 타고 들어가면서 건설시간을 더해준다.

 

이때, 현재의 건물 짓는 순서 우선순위에 맞는 건물들만 더해준다.

 

또한 같은 우선 순위에 있는 건물의 건설시간중에서 가장 큰 시간을 더해준다.
이유는 모든 건물이 완성되어야지만, 원하는 건물을 지을수 있기 때문이다.

 

 

기능 목록 📲

 

1. 값들을 저장할 배열들을 선언한다.

 

const [N, K] = input[input_idx].split(" ").map(Number);
  input_idx += 1;
  const spendTime = input[input_idx].split(" ").map(Number);
  let buildOrder = Array.from({ length: N + 1 }, () => []);
  let rank = Array.from({ length: N + 1 }, () => 0);
  let spendTotal = Array.from({ length: N + 1 }, () => 0);

 

buildOrder => 건물 순서를 저장할 배열이다. 부모 -> 자식  단방향으로 저장한다.

 

rank => 건설 우선순위를 저장할 값이다. 뒤쪽에 많이 나올수록 후순위로 밀려난다.

 

spendTotal => DP 를 진행해가면서 누적 건설시간을 저장할 공간이다.

 

 

 

2. 입력값에 따라 배열을 채워주고, 우선순위를 매겨준다.

 

  for (let j = 0; j < K; j++) {
    const [front, back] = input[input_idx + j].split(" ").map(Number);
    buildOrder[front].push(back);
    rank[back] += 1;
  }

 

 

3. 우선순위가 0번이라면 루트노드이다. 루트노드를 찾는다.

 

rank.forEach((v, idx) => {
    if (v === 0 && idx !== 0) {
      queue.push(idx);
      spendTotal[idx] = spendTime[idx - 1];
    }
  });

 

루트노드를 우선적으로 건설해야함으로 queue에 담아준다.

 

 

4. queue 를 돌면서 동일한 우선순위에 있는 건설시간들을 spendTotal에 초기화시킨다.

 

while (queue.length !== 0) {
    let nowBuild = queue.shift();
    for (let nextBuild of buildOrder[nowBuild]) {
      rank[nextBuild] -= 1;
      spendTotal[nextBuild] = Math.max(
        spendTotal[nowBuild] + spendTime[nextBuild - 1],
        spendTotal[nextBuild]
      );

      if (rank[nextBuild] === 0) {
        queue.push(nextBuild);
      }
    }
  }

 

이때, 이미 spendTotal에 값이 담겨있을 수도 있으므로 이전 건설시간 총합 +건설할 건물의 건설시간 과 이미 담겨있는 spendTotal의 값들 중 가장 큰 값을 부여한다.

 

우선 순위가 0번 째라면 다음 건설할 건물이므로 queue 에 넣어준다. 

 

 

 

 

 

정답 💯

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const T = Number(input[0]);
let input_idx = 1;
let loop = 0;
while (loop < T) {
  const [N, K] = input[input_idx].split(" ").map(Number);
  input_idx += 1;
  const spendTime = input[input_idx].split(" ").map(Number);
  let buildOrder = Array.from({ length: N + 1 }, () => []);
  let rank = Array.from({ length: N + 1 }, () => 0);
  let spendTotal = Array.from({ length: N + 1 }, () => 0);
  input_idx += 1;
  for (let j = 0; j < K; j++) {
    const [front, back] = input[input_idx + j].split(" ").map(Number);
    buildOrder[front].push(back);
    rank[back] += 1;
  }
  input_idx += K;
  let W = Number(input[input_idx]);
  let queue = [];
  rank.forEach((v, idx) => {
    if (v === 0 && idx !== 0) {
      queue.push(idx);
      spendTotal[idx] = spendTime[idx - 1];
    }
  });
  while (queue.length !== 0) {
    let nowBuild = queue.shift();
    for (let nextBuild of buildOrder[nowBuild]) {
      rank[nextBuild] -= 1;
      spendTotal[nextBuild] = Math.max(
        spendTotal[nowBuild] + spendTime[nextBuild - 1],
        spendTotal[nextBuild]
      );

      if (rank[nextBuild] === 0) {
        queue.push(nextBuild);
      }
    }
  }
  console.log(spendTotal[W]);
  input_idx += 1;
  loop += 1;
}