알고리즘 - 유니온 파인드

유니온 파인드

두 노드가 같은 그래프에 속하는지 판별하는 알고리즘

• 연산
  Find 연산 - 루트 노드를 찾는 연산 , 시간 복잡도 : O(1)
  Union 연산 - 노드를 합치는 연산

• 특징

  • 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불림
  • 트리 구조로 이루어진 자료구조
  • 최소신장트리를 구하는 크루스칼 알고리즘에서 사용

👉 노드 번호와 부모 노드로 초기화된 노드들을
Union 연산을 통해 부모노드와 자식연산 구분

연산 방법

Union 연산

x-y 연결
x와 y의 루트 노드를 찾아 비교하기

union(x,y)
	x = find(x)	//x 루트
    y = find(y)	//y 루트
    if x! = y	// y와 x의 루트가 같지 안으면
    	//값이 작은쪽을 부모로 둔다
    	if x<y -> parent[y] = x 
        else -> parent[x] = y

Find 연산

할당 연산을 이용해서 편향트리가 되지 않도록 균형을 잡아줌

find(x) // x의 루트 노드 찾기
	if x == parent -> return x
    return parent[x] = find(parent[x])

참고문제
백준 1717 - 집합의 표현
백준 1976 - 여행가자