728x90
반응형
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이 나오게 된다.
반응형
댓글