[Javascript][BOJ] 10423 전기가 부족해

www.acmicpc.net/problem/10423

10423번: 전기가 부족해

 

핵심아이디어.

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

다만, 특별한 점이 있다면 각 노드들이 발전소가 있는 도시와 일반도시로 나누어 진다는 것이다.

일반 도시들은 발전소에서 전기를 끌어와야 하므로, 모든 발전소 도시들의 미리 union으로 묶어놓고

크루스칼/유니온파인드 알고리즘을 사용하면 된다.

 

'use strict'

const readline = require("readline");
const {
    appendFile
} = require("fs");
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, k] = input.shift().split(" ").map(elem => parseInt(elem))
    const powerPlants = input.shift().split(" ").map(elem => parseInt(elem));
    const edges = [];
    let parents = [...new Array(n + 1)].map((_, idx) => idx);
    let res = 0;
    for (const edge of input) {
        const [u, v, w] = edge.split(" ").map(elem => parseInt(elem));
        edges.push([u, v, w]);
    }

    // 발전소끼리는 모두 union으로 묶어준다.
    for (let i = 0; i < powerPlants.length - 1; i++) {
        const powerPlant = powerPlants[i];
        const nextPowerPlant = powerPlants[i + 1];
        parents = union(parents, powerPlant, nextPowerPlant);
    }

    edges.sort((a, b) => a[2] - b[2]);
    // console.log(edges);
    edges.forEach((edge) => {
        const [u, v, w] = edge;
        if (findParent(parents, u) !== findParent(parents, v)) {
            // console.log();
            // console.log(findParent(parents, u), findParent(parents, v))
            parents = union(parents, u, v);
            // console.log(u, v);
            res += w;
        }
    });
    // console.log(parents);
    console.log(res);
};


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