크루스칼 알고리즘 (Kruskal Algorithm)

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

• 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘
• 핵심 개념
  • 간선을 거리가 짧은 순서대로 그래프에 포함시키기!
  • 사이클이 형성되지 않도록
• 사이클이 발생하는지 여부 -> Union-Find 알고리즘

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

프로그래머스

# 부모 찾기
def find_parent(parent,i):
    if parent[i] != i:
        parent[i] = find_parent(parent,parent[i])
    return parent[i]

# 연결될 경우 부모 일치시키기
# 더 작은 부모로 일치시키기
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


def solution(n, costs):
    # 부모 테이블
    parent  = [i for i in range(n)]
    
    # 비용이 적게 드는 순으로 확인
    costs.sort(key=lambda x:x[2])
    
    total_cost = 0
    
    for i in range(len(costs)):
        a, b, money = costs[i]
        # 사이클이 연결되는지 확인
        # 사이클이 생기지 않는다면
        if find_parent(parent,a) != find_parent(parent,b):
            union_parent(parent,a,b)
            total_cost += money
    return total_cost