프로그래머스 섬 연결하기

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

처음 보고서 학교 알고리즘과목 시간에 배웠던 크루스칼 알고리즘이 떠올랐다.
크루스칼 알고리즘은 union-find알고리즘을 통해서 구현할 수 있다.

크루스칼 알고리즘은 비용이 작은 간선부터 고르면서 사이클을 만들지 않으면서 모든 정점을 연결하는 것이다.
union-find 알고리즘은 disjoint set을 만드는 알고리즘에 속하는데,

disjoint set

• 서로 중복되지 않는 부분 집합들 로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 공통 원소가 없는, 즉 “상호 배타적” 인 부분 집합들로 나눠진 원소들에 대한 자료구조이다.
  Disjoint Set = 서로소 집합 자료구조

union-find알고리즘은 전체 집합에 대해서 구성 원소들이 겹치지 않게 "분할"하는데 주로 사용된다.
위의 크루스칼 알고리즘에서 union-find알고리즘은 사이클을 만들지 않기 위해 정점과 간선의 연결 집합을 겹치지 않게 하기 위해 사용된다.

def solution(n, costs):
    costs.sort(key = lambda x: x[2])
    p = [0]
    for i in range(1,n+1): ## 처음 부모노드는 자기자신
        p.append(i)
    def union(x,y): ## 정점의 부모를 찾고 연결
        root1 = find(x)
        root2 = find(y)
        p[root2] = root1
        
    def find(x): ## 부모노드찾기
        if p[x] == x:
            return x
        else:
            return find(p[x])
    
    edges = 0
    answer = 0
    for info in costs:
        if edges == n-1:
            break;
        else:
            a,b,cost = info
            if find(a) != find(b): ## 서로소 집합인 경우에는 union으로 합침
                union(a,b)
                edges += 1
                answer += cost
            
    return answer