최소 신장 트리 (MST)

1. 크러스컬 알고리즘 구현

- Union, Find 함수 구현하여 활용

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

# MST 최소 신장 트리 문제
def find(parent, x):
    # 루트 노드를 찾는 함수
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    # 두 서브트리를 합치는 함수
    a = find(parent, a)
    b = find(parent, b)
    print(f"합치기 전: {parent}")  # 합치기 전 상태 출력
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    print(f"합친 후: {parent}")  # 합친 후 상태 출력

def solution(n, costs):
    # 초기화
    parent = [0] * n
    for i in range(n):
        parent[i] = i
    
    # 다리 건설 비용을 기준으로 오름차순 정렬
    costs.sort(key=lambda x: x[2])
    answer = 0
    for cost in costs:
        a, b, c = cost
        # 사이클이 발생하지 않는 경우, 즉 두 노드의 루트 노드가 다른 경우에만 선택
        # 각 노드의 부모 노드가 같은데 두 노드를 union한다면 사이클이 발생함.
        if find(parent, a) != find(parent, b):
            union(parent, a, b)
            answer += c
    
    # 모든 연결 과정이 끝난 후의 parent 배열 상태 출력
    print(f"최종 parent 배열: {parent}")
    return answer