[Javascript] 내가 쓰려고 만든 자바스크립트 최소 스패닝 트리/크루스칼/유니온 파인드

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

위 문제를 풀 때 사용한 코드입니다.

자바스크립트는 원래 call by value이기 떄문에 아래 unionFind할때 배열 전체를 덮어씌우는 작업이 오래걸릴 줄 알고

class형으로 짜봤는데 오히려 시간이 더 늘어났습니다. (이유가 뭐지?)

 

'use strict'

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


function findParent(parent, x) {
    if (parent[x] !== x) {
        parent[x] = findParent(parent, parent[x]);
    }
    return parent[x];
}

function unionFind(parent, a, b) {
    a = findParent(parent, a);
    b = findParent(parent, b);
    if (a < b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
    return parent;
}

const solution = function (input) {
    const [V, E] = input[0].split(" ").map(e => parseInt(e));
    const edges = [];
    let parents = new Array(V + 1);
    let res = 0;
    for (let i = 0; i <= V; i++) {
        parents[i] = i;
    }
    for (let i = 0; i < E; i++) {
        const [a, b, c] = input[1 + i].split(" ").map(e => parseInt(e));
        edges.push([a, b, c]);
    }

    edges.sort((a, b) => a[2] - b[2]);

    edges.forEach(
        edge => {
            const [a, b, c] = edge;
            if (findParent(parents, a) !== findParent(parents, b)) {
                parents = unionFind(parents, a, b);
                res += c;
            }
        }
    );
    console.log(res);
};


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