union-find 알고리즘

Union-Find 알고리즘이란?

Union-Find 알고리즘은 그래프 알고리즘 중 하나로

 

서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불린다.

 

여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

Union-Find 과정

1) Init

 

for(int i = 0; i < parent.length; i++) parent[i] = i;

초기화. 최초 노드는 자기자신을 루트노드로 가진다.

 

1) Find(x)

// x가 속한 그래프의 루트 노드를 반환 
	static int find(int x) {
		// x의 루트노드가 x일 경우. 즉, x와 연결된 노드가 없을 경우.
		if(x == parent[x]) return x;
		
		// 재귀를 이용해 부모노드 -> 부모노드 ->...->루트노드의 방식으로 루트노드를 찾아 반환한다.
		return find(parent[x]);
	}

x가 속한 집합(그래프)의 root 노드를 반환한다.

 

2) Union(x, y)

// x와 y가 속한 두 그래프를 하나로 합친다. 
	static void union(int x, int y) {
		// 두 노드의 루트노드를 찾는다.
		x = find(x);
		y = find(y);
		
		// 두 루트노드 중 원소 값이 더 작은 루트노드를 그래프의 루트노드로 선택한다. 
		if(x > y) parent[x] = y;
		else parent[y] = x;
	}

x가 속한 집합(그래프)와 y가 속한 집합(그래프)를 합친다.

 

Union-Find 시간 복잡도

일반적으로 유니온파인드를 사용하게 될 경우, 평균적으로 트리의 높이만큼 탐색하는 O(logN)이지만, 트리를 형성하는 과정에서 사향트리(Skewed Tree)가 될 수 있으며, 이렇게 될 경우 시간 복잡도는 O(n)이 되어버린다.

 

따라서, 효율성을 위해 Find 과정에서 경로 압축을 할 수 있다. 경로 압축을 하게 될 경우, find 함수를 호출 시 마다 트리의 높이가 매번 달라지게 되므로 수행시간이 변화게 된다.

 

경로 압축을 한 find의 시간 복잡도는 O(a(N))이 되는데 여기서 a(N)은 아커만 함수를 의미한다. 

아커만 함수에서 N이 2^65536일 때, 아커만 함수의 값은 5가 되므로 상수의 시간 복잡도를 가진다고 봐도 무방하다.

 

1) Find(x)

// x가 속한 그래프의 루트 노드를 반환 
	static int find(int x) {
		// x의 루트노드가 x일 경우. 즉, x와 연결된 노드가 없을 경우.
		if(x == parent[x]) return x;
		
        // 재귀를 이용해 최상위노드를 찾는 과정에서 경로 최적화를 실시
		return parent[x] = find(parent[x]);
	}

 

2) Union(x, y)

// x와 y가 속한 두 그래프를 하나로 합친다. 
	static void union(int x, int y) {
		// 두 노드의 루트노드를 찾는다.
		x = find(x);
		y = find(y);
        
        if(x == y) return;
        if(rank[x] < rank[y]) parent[x] = y;
        else parent[y] = x;
        if(rank[x] == rank[y]) rank[x]++;
	}

 

너비 우선 탐색 구현

package baekjoon;

import java.util.*;
import java.io.*;
public class BOJ_2606 {
	static int[] parent;
	
	public static int find(int x) {
		if(x == parent[x]) return x;
		int y = find(parent[x]);
		parent[x] = y;
		return y;
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x != y) parent[y] = x;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tk = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(tk.nextToken());
		tk = new StringTokenizer(br.readLine());
		int e = Integer.parseInt(tk.nextToken());
		int cnt = 0;
		
		parent = new int[v + 1];
		for(int i = 1; i <= v; i++) {
			parent[i] = i;
		}
		
		for(int i = 0; i < e; i++) {
			tk = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(tk.nextToken());
			int y = Integer.parseInt(tk.nextToken());
			union(x, y);
		}
		
		for(int i = 2; i <= v; i++) if(find(1) == find(i)) cnt++;
		System.out.println(cnt);
	}
}