[자료구조] - 유니온 파인드 (Union-Find)

크루스칼(Kruskal) 알고리즘을 진행하던 도중 헷갈려 글을 쓰게 되었다

💫 유니온 파인드란?

ㆍ두 노드가 같은 집합에 속하는지 판별한다.
ㆍ'합집합 찾기' 라는 의미를 가졌으며 서로소 집합(공통 원소가 없는 집합들) 알고리즘이라고도 부른다.
ㆍKruskal 알고리즘에서 최소 신장 트리를 찾을 때 유용하게 사용된다.

👩🏻‍💻 union,find 연산을 완벽히 이해해야 한다
ㆍUnion(합집합): 두 개의 노드가 포함된 집합을 하나로 합치는 연산
ㆍFind(찾기): 자신이 속한 집합의 루트 노드를 반환하는 연산

💫 Find 연산

해당 노드의 부모 노드와 해당 노드를 비교한다.
두 노드가 같은 경우, 해당 노드는 루트 노드이다.

같지 않다면 해당 노드의 부모 노드에 대하여 find 연산을 재귀호출한다.

public UnionFind(int size) {
        parent = new int[size];
        // 초기화: 각 원소의 부모를 자기 자신으로 설정
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }


public int find(int x) {  
		//x의 집합의 루트를 찾습니다
		//x가 자신의 부모가 아닌 경우에는 x를 parent[x]로 업데이트하여 계속해서 부모 찾기
 		if (parent[x] != x) {
            parent[x] = find(parent[x]); 
        }
        return parent[x];
    }

💫 Union 연산

두 노드에 대해 Find연산을 각각 수행하여, 두 노드가 각각 속한 집합의 루트 노드를 찾아낸다.

    public void union(int x, int y) {
        int rootX = find(x); //x의 집합의 루트
        int rootY = find(y);
        if (rootX != rootY) {  //x와 y가 같은 집합에 속해 있지 않은 경우
            parent[rootY] = rootX; // y의 루트를 x의 루트로 설정
        }
    }

💫 전체 코드

class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size];
        // 초기화: 각 원소의 부모를 자기 자신으로 설정
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    // find 연산: 루트를 찾음 (경로 압축을 사용한 재귀 버전)
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축을 통해 루트를 찾고 부모 업데이트
        }
        return parent[x];
    }

    // union 연산: 두 원소를 하나의 집합으로 합침
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX; // y의 루트를 x의 루트로 설정
        }
    }

    // 연결 여부 확인
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

// 예제 사용
public class Main {
    public static void main(String[] args) {
        int n = 6; // 원소의 개수
        UnionFind uf = new UnionFind(n);

        // 간선 추가
        uf.union(1, 2);
        uf.union(2, 3);
        uf.union(4, 5);

        // 연결 여부 확인
        System.out.println("1과 3이 같은 집합에 속해 있는가? " + uf.isConnected(1, 3)); // true
        System.out.println("1과 5가 같은 집합에 속해 있는가? " + uf.isConnected(1, 5)); // false
    }
}

출력값

1과 3이 같은 집합에 속해 있는가? true
1과 5가 같은 집합에 속해 있는가? false