99클럽 코테 스터디 16일차 TIL + 섬 연결하기

### 유니온 파인드 + 크루스칼 알고리즘

def find_parent(x, parent):
    if x!=parent[x]:
        x = find_parent(parent[x],parent)
    return parent[x]

def union(a,b,parent):
    a=find_parent(a,parent)
    b=find_parent(b,parent)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

def solution(n, costs):
    answer = 0
    costs.sort(key=lambda x:(x[2]))
    parent=[i for i in range(n)]
    for a,b,c in costs:
        ## 부모의 노드가 서로 다르면 싸이클이 발생하지 않음 
        ## => union 연산 수행해 최소 신장 트리에 추가
        if find_parent(a, parent)!=find_parent(b,parent):
            union(a,b,parent)
            answer+=c
            
    return answer