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

유니온-파인드 (Union-Find)

- 대표적인 그래프 알고리즘

- 두 노드가 같은 집합에 속하는지 판별하는 알고리즘

- 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과

   두 노드가 같은 집합에 속해 있는지 확인하는 find연산으로 구성되어 있는 알고리즘

 

🌝 작동원리

1. 대상 노드 배열에 index값과 value값이 동일한지 화긴

2. 동일하지 않으면 value값이 가르키는 index위치로 이동

3. 이동 위치의 index값과 value값이 같을 때까지 1번과 2번 반복 => 재귀 함수로 구현

4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경

 

// 참고 https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
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