[Javascript][BOJ] 14950 정복자

www.acmicpc.net/problem/14950

14950번: 정복자

 

핵심 아이디어.

기본적인 최소 스패닝 트리의 크루스칼 알고리즘을 사용하면 된다

추가적인 조건이 있다면 union을 1번 할 수 록 다른 모든 간선에 t만큼 비용이 추가된다.

모든 간선에 같은 값이 추가되므로, edge를 선택하는 순서에는 변화가 생기지 않으므로

비용을 더해줄때 누적된 t값을 추가적으로 더해주기만 하면된다.

 

'use strict'

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const findParent = (parents, target) => {
    if (parents[target] !== target) {
        parents[target] = findParent(parents, parents[target]);
    }
    return parents[target];
}

const union = (parents, a, b) => {
    a = findParent(parents, a);
    b = findParent(parents, b);
    if (a, b) {
        parents[b] = a;
    } else {
        parents[a] = b;
    }
    return parents;
}

const solution = function (input) {
    const [n, m, t] = input.shift().split(" ").map(elem => parseInt(elem));
    const edges = input.map(edge => edge.split(" ").map(elem => parseInt(elem)));
    let parents = [...new Array(n + 1)].map((_, idx) => idx);
    let additionalCost = 0;
    let res = 0;
    edges.sort((a, b) => a[2] - b[2]);
    for (const edge of edges) {
        const [a, b, c] = edge;
        if (findParent(parents, a) !== findParent(parents, b)) {
            parents = union(parents, a, b);
            res += (c + additionalCost);
            additionalCost += t;
            // console.log(a, b);
        }
    }
    console.log(res);
};


const input = [];
rl.on("line", function (line) {
    input.push(line);
}).on("close", function () {
    solution(input);
    process.exit();
});