[JavaScript] 백준 1005 ACM Craft(JS)

ACM Craft

📚 문제 설명

자세한 문제 설명은 문제 링크 참고.

건물들의 연결 관계가 주어진다. 건물에는 순서가 존재한다.
만약 앞선 순서의 건물이 완공되지 않았다면, 건물을 지을 수 없다.
N번 건물을 짓는데 걸리는 시간은 얼마나 걸리는가?

👨🏻‍💻 풀이 과정

이렇게 순서가 있는 정렬에는 이전에 풀었던 선수과목 문제에서 했던 위상 정렬을 사용하면 된다.
위상정렬의 자세한 설명은 위의 선수과목 문제 링크로 확인하고 간략하게 로직 설명만 하겠다.

• 각각의 노드로 들어오는 선의 갯수를 저장.
• 들어오는 선이 0인 노드 먼저 실행 시작.
• BFS문과 유사하게 진행.
• 다음 노드에 들어오는 간선이 0이면 Queue에 삽입.
• 현재 확인 중인 노드가 목표 노드라면 종료.

전체 코드

    let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");

    const TESTCASE = parseInt(input[idx++]);
    for (let i = 0; i < TESTCASE; i++) {

    const [B, L] = input[idx++].split(' ').map(Number);
    // 각각의 건물을 짓는데 걸리는 시간.
    const BuildDuration = input[idx++].split(' ').map(Number);
    // 간선.
    const inputLines = input.splice(idx, L);
    // 목표.
    const Target = parseInt(input[idx++]);

    let lines = Array.from({length: B}, _ => []);
    // 간선, 들어오는 선 갯수 갱신.
    let nodeCounter = Array.from({length: B}, _ => 0);
    inputLines.forEach(v => {
        const [Start, End] = v.split(' ').map(Number);
        lines[Start - 1].push(End - 1);
        nodeCounter[End - 1]++;
    });

    // 위상 정렬.
    const TopologicalSort = () => {
        let Queue = [];
        let timeArr = Array.from({length: B}, _ => 0);
      	// 들어오는 간선이 0개인 노드 큐에 삽입.
        for (let i = 0; i < B; i++) {
            if (nodeCounter[i] === 0) {
                Queue.push([i, 0]);
            }
        }

        let idx = 0;
        while (Queue.length > idx) {
            const [now, time] = Queue[idx];
          	// 목표 도착시 종료.
            if (now === Target - 1) {
                console.log(time + BuildDuration[now]);
                return;
            }

            for (const next of lines[now]) {
              	// 간선 갯수 -1.
                nodeCounter[next]--;
              	// 최대시간 갱신.
                timeArr[next] = Math.max(timeArr[next], time + BuildDuration[now]);
              	// 들어오는 간선이 0개라면 큐에 삽입.
                if (nodeCounter[next] === 0) {
                    Queue.push([next, timeArr[next]]);
                }
            }
            idx++;
        }

    };
    TopologicalSort();
}

🧐 후기

오랜만에 위상 정렬 함수를 구현할 수 있었던 좋은 문제였다.
한가지 다른 점은 최대 시간을 저장하는 부분에서 조금 고민이 많았었다.