[python]유니온파인드 알고리즘_이것도 알아야해?

 

 

유니온 파인드 : 

노드를 UNION하고 부모를 FIND해서 서로소 집합을 찾아내는 알고리즘 

 

 

UNION연산은 두 원소를 뽑아 원소가 포함된 집합의 부모노드를 비교한다. 

만약 다르다면 같은 부모를 가리키도록 만든다.

 

FIND 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.  

 

 

부모노드를 찾아 반환하게 만들면 전부 돌면서 찾아야하는 수가 있다. (시간이 너무 오래걸릴수도)

그래서 일일이 거슬러 부모노드를 찾는 것보다 한번에 빠르게 부모 노드에 갈 수 있도록 하는 경로 압축기법을 사용하면 빠르다.   < 해당 노드의 루트노드가 부모노드가 되게 만들어주면된다.>

 

 

 

---

 

 

코드 : 

def union(a,b) :
    a = find(a)
    b = find(b)
    if a > b :
        parent[a] = b 
    elif a < b :
        parent[b] = a
        
def find(x) :
    if x!=parent[x] :
    	# 경로압축
        parent[x] = find(parent[x])
    return parent[x]

 

 

 

 

 

---

 

 

 

 

 

관련 문제 : 

백준 _ 여행가자 : https://www.acmicpc.net/problem/1976

1976번: 여행 가자

내 포스팅 : https://what-am-i.tistory.com/372

[Python/BOJ] 백준 1976 여행가자_유니온파인드