[Programmers] 섬 연결하기

섬을 연결하는 최소 신장 트리를 구하는 문제이다.

문제 해결 전략
최소 신장 트리를 구하는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재한다.

이 문제에서는 간선과 간선을 이루는 노드가 주어졌으므로 크루스칼 알고리즘을 활용하였다.

크루스칼 알고리즘을 적용하기 위해 우선 간선의 길이를 기준으로 오름차순으로 정렬한다.

그리고 나서 알고리즘을 적용해 준다.

이 때 사이클 여부를 판단하기 위해 Union&Find 자료구조를 활용해야 한다.

우선 각 노드들의 부모를 자기 자신으로 초기화 해 준다.

그리고 나서 간선의 양 끝 노드들의 부모를 찾아 비교한 후 다르다면 더 작은 부모로 부모를 바꿔준다.

만약 두 노드들의 부모가 같다면 사이클이 생성되므로 그냥 넘어간다.

코드

function solution(n, costs) {
    var answer = 0;
    
    costs.sort(function(a,b){
        return a[2] - b[2]
    })
    
    const parent = new Array(n);
    for(let i=0;i<n;i++)
        parent[i] = i;

    const findParent = (elem) => {
        if(elem == parent[elem])
            return elem;
        return parent[elem] = findParent(parent[elem]);
    }
    
    costs.forEach((cost) => {
        const s = cost[0];
        const e = cost[1];
        const dis = cost[2];
        
        const sp = findParent(s);
        const ep = findParent(e);
        if(sp == ep)
            return;
        const np = Math.min(sp,ep);
        parent[sp] = np;
        parent[ep] = np;
        answer += dis;
    })
    
    return answer;
}

출처
https://programmers.co.kr/learn/courses/30/lessons/42861