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

🔹 유니온 파인드(Union-Find) 알고리즘이란 ?

• 트리/그래프의 대표적 알고리즘으로, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
• 상호 배타적 집합, 서로소 집합(Disjoint-Set)으로도 불린다.
• 노드를 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.

 

🔹 유니온 파인드 구현 - JAVA

[ find 연산 ]

private static int find(int x) {
	if (parents[x] == x) return x;
	return parents[x] = find(parents[x]);
}

• 특정 노드가 속한 집합의 루트 노드를 반환하는 연산이다.
• 해당 노드의 부모 노드와 해당 노드를 비교한다. 이때 두 노드가 같은 경우, 해당 노드는 루트 노드이다.
• 만약 같지 않다면, 해당 노드의 부모 노드에 대하여 find 연산을 재귀적으로 호출한다.

[ union 연산 ]

public static boolean union(int x, int y) {
    x = find(x);
    y = find(y);
    
    if (x == y) return false;
    
    if (x < y) parents[y] = x;
    else parents[x] = y;
    return true;
}

• 두 개의 노드가 포함된 집합을 하나의 집합으로 합치는 연산이다.
• 두 노드에 대해 find 연산을 각각 수행하여, 두 노드가 각각 속한 집합의 루트 노드를 찾아낸다.
• 이미 같은 집합에 있다면 false를 반환하고, 다른 집합에 속해있다면, 더 작은 루트 노드를 기준으로 합쳐준다.

 

 

 

 

 

📃 reference

• https://velog.io/@suk13574
• https://velog.io/@jiwon_choi