Union-Find (Disjoint Sets) 알고리즘

Union - Find랑 크루스칼 알고리즘을 사용하려면 필수적으로 알아야하는 알고리즘이다.

여러개의 노드가 존재할때 두 개의 노드를 선택하여 같은 트리에 포함되어있는지 확인하는 것이다.

Union - Find 를 구현할 때는 트리 자료구조를 이용하여 집합을 표현한다. 트리로 부분집합을 표현하고 find를 통해 루트 노드를 찾고 union으로 트리를 합친다.

 

처음 시작할때 숫자들은 자기 자신이 부모이며, 노드가 연결되어있어 합치게 되면 더 작은값이 부모가 된다.

만약 1,2 가 연결되어있으면 부모는 1,1 이다.

 

 

 

def find(parent, x):
    if parent[x] != x: # 자기 자신이 아닌경우 다른 노드에 연결된 경우
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent,x,y):
    x = find(parent,x)
    y = find(parent,y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
        
        
def solution(n,consts):

    cost = sorted(consts,key = lambda x:x[2])
    parent = [i for i in range(n+1)]
    answer =0
    for x,y,z in cost:
        if find(parent,x) != find(parent,y):
            union(parent,x,y)
            answer += z
    return answer

 

이 문제는 크루스칼알고리즘에서 쓰이는 유니온파인드 알고리즘을 가져왔다.

 

여기서 find, union 을 기본으로 하여 사용한다.

cost에서 간선인 x,y 와 가중치 z를 뽑아오는데

x와 y 가 연결된다. 연결이 되면 합집합이 되는것인데 그래서 find로 부모를 확인하여 부모값을 갱신해주면서 가중치를 합해주는것이다.

 

근데 find에서 재귀호출을 하는데 이 부분은 경로압축을하는것이다.

만약 1>4>6 이 연결되어있으면 압축경로를 사용하지 않으면 6의 부모는 4로 나온다.

하지만 재귀를 통해 부모를 계속 호출하여 최신화 시키므로 1이 나오게 된다.