Kruskal (MST): Really Special Subtree

사이트: HackerRank
난이도: 미디움
분류: Graph Theory

문제

각 간선과 가중치가 주어졌을 때 모든 노드들을 연결하여 최소 가중치를 가지는 값을 반환하라.

1. 나의 풀이

해당 문제는 최소신장 트리의 kruscal algorithm을 사용하여 해결하는 문제이다. kruscal algorithm을 잘 알고 있다면 기본적인 풀이방법으로 충분히 해결 가능한 문제라서 어렵지 않았다.

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

    return parent[x] = find(parent, parent[x]);
}

function union(parent, a, b) {
    a = find(parent, a);
    b = find(parent, b);

    if (a < b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
}

function compare(parent, a, b) {
    a = find(parent, a);
    b = find(parent, b);
    return a === b;
}

function kruskals(gNodes, gFrom, gTo, gWeight) {
    const parent = Array.from(new Array(gNodes), (_, i) => i);
    const sortedCosts = gFrom
        .map((f, i) => ([f, gTo[i], gWeight[i]]))
        .sort((c1, c2) => c1[2] - c2[2]);
        
    let answer = 0;
    for (const [a, b, cost] of sortedCosts) {
        if (!compare(parent, a, b)) {
            answer += cost;
            union(parent, a, b);
        }
    }
    
    return answer;
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.