[크루스칼] 섬 연결하기

크루스칼 알고리즘이란

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.

최소비용신장 트리를 만들기 위한 대표적 알고리즘으로 그래프에서 모든 노드를 연결할때 적용된다.

 

1. 우선 비용 오름차순으로 정렬한다.

2. 작은 비용의 선부터 연결하면서 Union find를 통해 신장트리가 되는지 확인한다

이때 이미 연결된 노드는 연결하지 않고 스킵한다

3. 모든 노드의 부모가 통일되면 최소비용신장트리가 완성된다.

 

 

 

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

프로그래머스

 

아직 크루스칼, 유니온 파인드를 모를때는 단순히 비용에 따라 오름차순으로 정렬하고 앞에서부터 n-1개만큼 비용의 합을 구했지만 간과한 것이 있었다.

이 말인 즉슨, 사이클이 생기면 안 된다는 것이다. (AB와 BC가 이미 연결됬는데 AC를 또 연결하면 사이클인 생긴다)

이미 같은 부모인데 또 union을 하면 => 사이클이 생김

 

개념을 이해한 뒤 다시 풀어봤다.

최소의 비용 => 비용에 따라 오름차순 정렬

사이클이 안 생기는 다리들의 비용을 더해간다.

function solution(n, costs) {
    var answer = 0;
    costs.sort((a, b) => a[2] - b[2]);
    // 자기자신을 parent로 두는 parents배열 만들기
    const parents = Array.from({length: n}, (_, i) => i);
    
    // 부모를 찾는 함수
    function getParent(a) {
        if (parents[a] === a) return a;
        return getParent(parents[a]);
    }
    // 같은 부모인지 확인하는 함수 (사이클이 생기는지 확인)
    function isSameParent(a, b) {
        return getParent(a) === getParent(b);
    }
    // 연결뒤 부모를 합치는 함수
    function unionParent(a, b) {
        a = getParent(a);
        b = getParent(b);
        
        if (a < b) parents[b] = a;
        else parents[a] = b;
    }
    
    for (const [a, b, cost] of costs) {
        // 같은 부모가 아니면, 즉 사이클이 생기지 않으면 연결
        if (!isSameParent(a, b)) {
            answer += cost;
            unionParent(a, b);
        }
        // 이미 연결되있음 스킵~
    }
    return answer;
}

 

유니온 파인드 + 크루스칼로 최소비용신장트리 문제를 해결할 수 있었다.