[알고리즘] 유니온-파인드 (자바)

유니온 파인드란?

말 그대로 union-find 알고리즘을 의미합니다.(주로 트리구조를 이용합니다.)

즉 집합-찾기 입니다.

같은 말로 disjoint-set이 있습니다.

 

 

사용 이유

1) 서로 다른 2개의 노드를 입력받아서  그 노드들을 합치거나,

2) find함수로 서로 다른 2개의 노드가 현재의 그래프에 속하는지 판별할 수 있습니다.

 

 

 

 

예제 코드

find 코드

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

union 코드

public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if( x != y ) {
			result[x] = y;
		}
	}

 

 

p.s

같이 풀어보면 좋은 백준 문제 번호 : 10775