유니온파인드

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

유니온 파인드 알고리즘이란? 💡유니온 파인드 알고리즘: 상호 배타적 집합, Disjoin-set(서로소 집합) 이라고도 부른다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어 주고, 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다. 왜 이름이 유니온 파인드인가? 유니온 파인드 알고리즘은 두가지의 연산을 진행한다. 이 연산 과정을 Union, Find라고 부른다. Union: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산을 말한다. 이 자료구조에서는 상호 배타적 집합만을 다루므로 Union 연산은 합집한 연산과 같다. Find: 하나읜 원소가 어떤 집합에 속해있는지를 판단한다. 크루스칼 알고리즘과 프림 알고리즘을 알기 위해선 유니온 파인드 알고리즘을 알아야 한다. 유니..