크루스칼 알고리즘

잔재미코딩 블로그 참고

모든 정점들을 가장 적은 비용으로 연결하기 위한 알고리즘

최소신장 트리

Spanning Tree: 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프. (트리의 속성: 사이클이 존재하지 않음)

Minimum Spanning Tree(MST):최소신장 트리. 가능한 Spanning Tree 들 중에서 간선의 가중치 합이 최소인 Spanning Tree

최소신장 트리를 찾는 방법으로는 크루스칼 알고리즘, 프림 알고리즘이 있다.

크루스칼 알고리즘

1. 모든 정점을 독립적인 집합으로 만든다
2. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양끝의 두 정점을 비교한다.
3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (사이클이 생기는 것을 방지)

(node 개수) - 1 의 간선개수로 최소신장 트리를 연결할 수 있다.
사이클이 발생하는 지의 여부는 Union-Find 알고리즘을 적용한다.

def solution(n, costs):
    answer = 0
    parent = [i for i in range(n)]
    def union(x,y):
        x = find(x)
        y = find(y)
        if x < y:
            parent[y] = x
        else:
            parent[x] = y
    def find(x):
        if parent[x] == x:
            return x
        return find(parent[x])
    
    costs.sort(key = lambda x : x[2])
    price = 0
    count = 0
    for s,e,c in costs:
        if find(s) != find(e):
            union(s,e)
            price += c
            count += 1
            if count == n + 1:
                return price

    return price
            
        
    
    return answer