[알고리즘] 유니온 파인드 : Union-Find (Disjoint Set)

Union-find? 그래프 알고리즘의 일종으로써, 상호 배타적 집합(Disjoint Set)이라고도 한다. 여러 노드가 존재할 때, 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 아래의 2가지 연산으로 이루어져 있다. Find: 노드 x가 어떤 집합에 포함되어 있는지 찾는 연산 Union: 노드 x와 노드 y가 포함되어 있는 집합을 합치는 연산 Union-find는 크루스칼 알고리즘에서 원소 간의 연결 여부를 판단하는 데에 사용한다. 구현 구현은 트리를 이용하며, parent[i]를 노드 i의 부모 노드라고 정의하고 초기화를 해준다. 이 때, parent[i] = i일 경우, 루트 노드임을 의미한다. int parent[MAX_SIZE];..

2020.08.03