[Java] union find (disjoint set)

union find (disjoint set)

• 공통된 원소가 없는 두 집합을 말합니다.
• '서로소 집합', 'disjoin set'으로 부르기도 합니다.
• Computer Science에서는 이 개념을 확장해 make, union, find 세 가지 연산으로 서로소 집합을 관리하는 자료구조를 의미합니다.
  1. make: 가지는 집합을 생성하는 연산
  2. find: 원소의 집합을 대표하는 원소(root 노드)를 찾는 연산
  3. union: 두 집합을 하나로 합치는 연산
  
  

union find 구현

parents 배열 : parents[x]는 x가 가리키는 부모 노드를 나타냅니다. 이 부모노드를 따라가다가 더이상 부모가 없는 root 노드를 만난다면 해당 노드가 집합을 대표하는 원소가 됩니다.

int[] parents = new int[N];  // N은 총 원소의 개수

1. make : 각 원소에 대해 독립적인 집합으로 초기화합니다.

for (int i = 0; i < N; ++i) {
	parents[i] = i;
}

2. find

int find(int x) {
	if (x == parents[x]) {
		return x;
	}
	
	/**
	 * (path compression)
	 * union 연산으로 대표 원소를 찾는데 가는 길이 멀어지는 경우를 방지하기 위해
	 * 대표 원소를 바로 가리키도록 만든다.
	 */
	return parents[x] = find(parents[x]);
}

3. union

void union(int x, int y) {
	int rootX = find(x);
	int rootY = find(y);
	
	if (rootX != rootY) {
		parents[rootX] = rootY;
	}
}

전체 코드 및 실행 예시

class UnionFind {
	int[] parents;  // parents[x] : x가 속한 집합의 대표 원소
	
	/* make 연산 (각 집합을 자기 자신 1개만 있는 집합으로 생성) */
	UnionFind(int N) {
		parents = new int[N];
		for (int i = 0; i < N; ++i) {
			parents[i] = i;
		}
	}
	
	/* find 연산 */
	public int find(int x) {
		if (x == parents[x]) {
			return x;
		}
		
		/**
		 * (path compression)
		 * union 연산으로 대표 원소를 찾는데 가는 길이 멀어지는 경우를 방지하기 위해
		 * 대표 원소를 바로 가리키도록 만든다.
		 */
		return parents[x] = find(parents[x]);
	}
	
	/* union */
	public void union(int x, int y) {
		int rootX = find(x);
		int rootY = find(y);
		
		/* x와 y가 서로 다른 서로소 집합에 속해 있는 경우 */
		if (rootX != rootY) {
			parents[rootX] = rootY;
		}
	}
}

public class Main {
	
	public static void main(String[] args) {
		UnionFind uf = new UnionFind(5);
		
		uf.union(0, 1);
		uf.union(1, 2);
		uf.union(3, 4);
		
		System.out.println("0과 3이 연결되어 있나요?");
		System.out.print(">> ");
		if (uf.find(0) == uf.find(3)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
		
		System.out.println("\n- 1이 속한 집합과 4가 속한 집합 연결\n");
		uf.union(1, 4);
		
		System.out.println("0과 3이 연결되어 있나요?");
		System.out.print(">> ");
		if (uf.find(0) == uf.find(3)) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

출력 결과

0과 3이 연결되어 있나요?
>> NO

- 1이 속한 집합과 4가 속한 집합 연결

0과 3이 연결되어 있나요?
>> YES

union find 활용

1. 사이클 판별

• 무방향 그래프에서 새로운 간선을 추가할 때 사이클이 형성되는지 판별할 수 있습니다.

  정점 $v_1$과 $v_2$에 새로운 간선을 추가하려는데 find(v1) == find(v2) 라면
  → 이미 다른 간선으로 연결되어 같은 집합에 속한다는 뜻이고, $v_1$과 $v_2$를 잇는 간선을 추가한다면 사이클이 형성됩니다.

• 사이클을 간단하고 효율적으로 판별할 수 있으므로 크루스칼 알고리즘으로 최소 신장 트리(Minimum Spanning Tree)를 구할 때 사용합니다.
  
  

2. 네트워크에서 연결성 파악

• 네트워크와 같이 동적으로 변화하는 집합들의 연결성을 관리하고 확인할 때 union find 알고리즘이 사용됩니다.

union find 연습하기

• SWEA 알고리즘 문제 중 union find를 위해 존재하는 문제가 있습니다. union find 는 이해하는 난이도에 비해 구현이 간단한 편이므로 이해를 완료하셨다면 쉽게 이 문제를 해결할 수 있을 것입니다.

  swea 3289 서로소 집합
  https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr

• Union Find 알고리즘은 그래프 이론에서 기본적이면서도 강력한 도구로, 복잡한 연결성 문제를 간단하고 효율적으로 해결할 수 있습니다. 위 연습 문제로 직접 구현해보고 실전에서도 활용해보시길 바랍니다!