UnionFind 알고리즘 개념과 구현

* UnionFind

- 유니온 파인드 알고리즘은 서로소 집합 ( Disjoint Set ) 을 관리하는 알고리즘

- 같은 그룹인지 판별 할때 쓰는 isConnected() 함수

- 두 그룹을 합칠떄 쓰는 Union() 함수를 사용한다.

 

1. 연결 요소가 존재하는가?

- isConnected() 함수의 로직은 2개의 node가 포함된 루트 노드가 같은지 다른지를 판단하여

같으면 연결 요소가 존재한다고 판단하고 True 반환. 다르면 연결 요소가 없다고 판단하여 False 반환.

 

2. Graph Cycle Detection

- union() 함수를 사용하여 2개의 node를 합칠때 두개의 node의 루트노드가 다를때 union 된다.

하지만 두개의 루트노드가 같을때 union 할시 Cycle 발생. 

- 즉 두개의 node의 루트노드가 같을때 Cycle 발생을 감지하게 됨.

 

* node의 루트노드를 찾는 find() 함수를 소개하고 전체 코드를 소개하겠다

private int find(int node) {
	if(node != parents[node]) {
    	parents[node] = find(parents[node]);
    }
    return parents[node];
}

 

* Path Compression ( 경로 압축 ) 을 이용한 루트 노드를 찾는 함수이다.

* 아래는 그 예시이다.

* 노드 5번을 집중하면 된다

* 노드 5번은 6번을 부모노드로 가지고있고 6번 노드는 2번노드를 부모노드로 가지고있다

* 하지만 find() 함수의 Path Compression 기법을 적용하면 5번 노드도 곧 바로 루트노드인 2번 노드를 가르키게 된다.

* 위 기법을 적용하여 나머지 isConnected() 함수와 Union() 함수를 구현하면 된다.

 

코드이다.

import java.io.*;
import java.util.*;

public class UnionFind {
    int[] parents;
    public static void main(String[] args) {
        UnionFind uf = new UnionFind(5);
        uf.union(1,2);
        uf.union(2,3);

        System.out.println(uf.isConnected(4,6));
    }

    public UnionFind(int node) {
        parents = new int[node+1];
        for(int i = 1; i <= node; i++) {
            parents[i] = i;
        }
    }

    public int find(int node) {
        if(node != parents[node]) {
            parents[node] = find(parents[node]);
        }
        return parents[node];
    }

    public void union(int node1, int node2) {
        int rootA = find(node1);
        int rootB = find(node2);

        if(rootA != rootB) {
            parents[rootB] = rootA;
        }
    }

    public boolean isConnected(int node1, int node2) {
        return find(node1) == find(node2);
    }
}

 

// 추후 업데이트 하겠다