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

Union-Find는 자료 구조입니다. 그래프 알고리즘에서 사용하는 대표 알고리즘입니다. 여러개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. Union-Find 알고리짐은 다른 고급 그래프 알고리즘의 베이스가 되니 반드시 학습하셔야 합니다.

 

동작과정

• 파인드(Find) : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 파인트는 일반적으로 어떤 원소가 속한 집합을 '대표'하는 원소를 반환하는데, 이를 위해서 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다.
• 유니온(Union) : 두 개의 집합을 하나의 집합으로 합친다.

시간복잡도

평균적으로 트리의 높이마큼 탐색하는 O(logN) 입니다.

참고사이트

https://m.blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

서로소 집합 자료 구조 - 위키백과, 우리 모두의 백과사전

 

기본코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class UnionFind_기본코드 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static char[] uArr = new char[100];

    static char getFind(char tar) {
        //최종보스가 누군지 리턴하는 함수        
        if (uArr[tar] == 0) return tar;        
        char ret = getFind(uArr[tar]);
        uArr[tar] = ret; //현재 보스를 최종보스로 교체
        return ret;        
    }

    static void setUnion(char t1, char t2)
    {
        char a = getFind(t1);
        char b = getFind(t2);
        if (a == b) return;
        uArr[b] = a;
    }

    public static void main(String[] args) throws IOException {        

        setUnion('A', 'B');
        setUnion('B', 'C');
        setUnion('E', 'D');        
        setUnion('F', 'E');        
        setUnion('G', 'H');        
        setUnion('I', 'J');        

        System.out.println("A:"+getFind('A'));
        System.out.println("B:"+getFind('B'));
        System.out.println("C:"+getFind('C'));
        System.out.println("D:"+getFind('D'));
        System.out.println("E:"+getFind('E'));
        System.out.println("F:"+getFind('F'));
        System.out.println("G:"+getFind('G'));
        System.out.println("H:"+getFind('H'));
        System.out.println("I:"+getFind('I'));
        
        //활용, A랑 E랑 같은 조직인지 확인하는 코드
        if (getFind('E') == getFind('D')) {
            System.out.println("같은조직");
        }
        else {
            System.out.println("다른조직");
        }

        br.close();
        bw.close();
    }
}