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

✔ 목차

1. 유니온 파인드란?
2. 유니온 파인드 예시
3. 유니온 파인드 구현 - Java

---

🔎 유니온 파인드란?

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

• 그래프/트리의 대표적 알고리즘
• 서로소인 부분집합의 표현
• 여러 노드가 있을 때, 두 노드가 같은 그래프에 속해있는지 알 수 있음
• union(x, y) 연산과 find(x) 연산으로 이루어져 있음
  • union(x, y) : x와 y그래프를 합친다.
  • find(x) : x가 어느 그래프에 속하는지 연산한다.
    
    

---

🔎 유니온 파인드 예시

노드 1부터 5까지 있는 그래프가 있다.

위의 그림에서 노드 5개는 서로 연결되지 않고있다. 이 때 부모는 자기 자신을 가르키도록 한다. 이 단계를 보통 부모노드 초기화라고 부른다.
x는 노드 번호이고, parent[x]는 x가 어떤 부모 노드에 속해있는지 알려준다.

1) union(1, 2)

• parent[2] = 1
  노드 1과 2를 연결해준다. 이 때 노드 번호가 작은 쪽이 부모가 되도록 한다.
  
  

2) union(3, 4) , union(3, 5)

• parent[4] = 3 , parent[5] = 3
  위와 동일한 방식으로 union을 해준다.

노드 2와 4의 부모 노드는 find로 찾을 수 있다.
find(2) = 1
find(4) = 3

3) union(2, 4)

• parent[3] = 1
  2가 속한 그래프와 3이 속한 그래프를 합친다. find(2) = 1이고, find(4) = 3이다. 노드 3은 노드 1보다 번호가 작으므로 노드 3의 부모노드는 1이 된다.

find(x)를 할 때 노드번호 x와parent[x]의 값이 같아야 하므로 노드 4의 find는 1이 된다.
find(4) = 1

---

💻 유니온 파인드 구현 - Java

union 연산

public static boolean union(int x, int y) {
	x = find(x); //x의 부모노드 찾기
	y = find(y); //y의 부모노드 찾기
    
	// 이미 같은 그래프에 속해있을 때 false 반환
	if(x == y) return false;
	
	if(x <= y) parent[y] = x;
	else parent[x] = y;
	return true;
}

find 연산

public static int find(int x) {
	if(parent[x] == x) return x;
	return find(parent[x]);
}

위의 예제 실행한 전체 코드

public class Main {
	static int[] parent;

	// union 연산
	public static boolean union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x == y) return false;
		
		if(x <= y) parent[y] = x;
		else parent[x] = y;
		return true;
	}
	
    // find 연산
	public static int find(int x) {
		if(parent[x] == x) return x;
		return find(parent[x]);
	}
    
     // parent 출력
	public static void parentPrint() {
		System.out.print("[ ");
		for (int i = 1; i < parent.length; i++) {
			System.out.print(parent[i]+ " ");
		}
		System.out.println("]");
	}

	public static void main(String[] args) {
		int n = 5;
		parent = new int[n + 1];
        // 부모 노드 초기화
		for (int i = 0; i < parent.length; i++) parent[i] = i;
		
        //위의 예제 실행
		union(1, 2);
		parentPrint();
		union(3, 4);
		parentPrint();
		union(3, 5);
		parentPrint();
		System.out.println("find(2): " + find(2));
		System.out.println("find(4): " + find(4));
		union(2, 4);
		parentPrint();
		System.out.println("find(4): " + find(4));
	}
}

출력 결과

[ 1 1 3 4 5 ]
[ 1 1 3 3 5 ]
[ 1 1 3 3 3 ]
find(4): 3
[ 1 1 1 3 3 ]
find(4): 1