Leta Learns

Union - Find (합집합 찾기) 대표적인 그래프 알고리즘 상호 배타적 집합 (Disjoint-Set) 알고리즘 (서로소 집합) 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여, 이 두 노드가 서로 같은 그래프에 속하는지 판별 2가지 연산으로 이루어져 있다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 그림으로 이해하기 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만든다. i : 노드번호 P[i] : 부모 노드 번호 ( => 자기 자신이 어떤 부모에 포함되어 있는지를 의미, parent) 지금 현재는 모든 값이 자기 자신을 가리키므로 P[i] = i 이다. Uni..