서로소 집합 자료구조
✅ 각 집합이 간선인 셈
✅ 서로소 판별을 위한 자료구조
✅ 합집합 : 두 원소가 포함되어있는 각각의 집합을 하나의 집합으로 합친다.
✅ 찾기 : 각 원소가 같은 집합에 포함되어 있는지에 대한 여부를 판단
ex. 각 원소가 속한 집합: 1 1 1 1 5 5 5 5 // A집합은 1~4노드, B집합은 5~8노드
기본 구현
동작 원리
✅ 초기에는 각 노드가 각각의 집합이므로 부모를 자기 자신으로 초기화
✅ 그림상 실제로는 루트노드끼리 연결 된 것을 확인할 수 있다.
✅ 해당 부모테이블은 그때그때의 루트 노드이므로, 최종값은 루트 값이 아닐 수 있다.
-> 따라서 3번노드와 4번노드는 그림 상 같은 집합이지만 테이블의 부모값은 다르다. (같은 집합인지 부모값 봐서는 판별 불가)
-> 별도로 루트노드 최종적으로 찾아야함
✅ 왼쪽 집합과 오른쪽 집합은 서로소 관계이다.
소스
package com.company;
import java.util.*;
public class Main {
// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
// 특정 원소가 속한 집합을 찾기 (루트노드 반환)
public static int findParent(int x) {
if (x == parent[x]) return x;
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
return findParent(parent[x]);
}
// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
// 1. a, b 각각의 그때 그때의 루트노드를 구하여
a = findParent(a);
b = findParent(b);
// 2. 루트노드끼리 연결
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
// Union 연산을 각각 수행
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
unionParent(a, b);
}
// 부모 테이블 내용 출력하기
System.out.print("부모 테이블: ");
for (int i = 1; i <= v; i++) {
System.out.print(parent[i] + " ");
}
System.out.println();
// 각 원소가 속한 집합 출력하기
System.out.print("각 원소가 속한 집합: ");
for (int i = 1; i <= v; i++) {
System.out.print(findParent(i) + " ");
}
System.out.println();
}
}✅ 입력예시
6 4
1 4
2 3
2 4
5 6
문제점
✅ 상단 최종 부모테이블 상태에서 특정 노드(5번)에 대해서 최종 find 연산(각 원소가 속한 집합 출력하기)을 수행하면 하단 출력 결과처럼 find함수가 최악의 경우 재귀적으로 5번(=노드 수 v) 호출된다.
public class Main {
public static int findParent(int x) {
if (x == parent[x]) return x;
System.out.println("parent["+x+"]를 인자로 받는 재귀함수 호출");
return findParent(parent[x]);
}
....
for (int i = 1; i <= v; i++) {
// 부모테이블 값을 바로 갱신
findParent(i);
System.out.print("부모 테이블: ");
for (int k = 1; k <= v; k++) {
System.out.print(parent[k] + " ");
}
System.out.println();
System.out.println("====================");
}
}
}
경로 압축 구현
동작 원리
✅ 최종 find 연산에서 부모테이블 값을 바로 갱신하도록 하여, 최종 find 연산을 최적화 (루트 노드까지 도달하기위한 경로를 압축)
✅ 최종 find함수를 매 노드마다 모두 호출 한 뒤 부모테이블의 결과는 모두 루트 노드로 갱신된다.
소스
import java.util.*;
public class Main {
public static int v, e;
public static int[] parent = new int[100001];
public static int findParent(int x) {
if (x == parent[x]) return x;
int tmp = findParent(parent[x]);
System.out.println("호출된 재귀함수의 결과 "+tmp+"가 parent["+x+"]에 저장 됨");
parent[x] = tmp;
return parent[x];
}
public static void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
unionParent(a, b);
}
for (int i = 1; i <= v; i++) {
// 부모테이블 값을 바로 갱신
findParent(i);
System.out.print("부모 테이블: ");
for (int k = 1; k <= v; k++) {
System.out.print(parent[k] + " ");
}
System.out.println();
System.out.println("====================");
}
}
}
✅ 최종 find함수가 호출 될 때, 매 노드에 대한 재귀호출 횟수가 최악의 경우에도 총 노드 수 보다 적게 호출되므로 시간복잡도가 줄어듦
참고
✅ 참고
