[Union-Find, Disjoint Set] 알고리즘 기본 코드 형식

Union-Find 알고리즘 기본 코드 형식

Union-Find 알고리즘 구현을 위해 알아두어야 할 코드 템플릿

- 코딩테스트와 같은 문제 해결을 위해서는 구현력이 매우 중요 

- 알고리즘에 대한 이해와 더불어 알고리즘 구현을 위한 기본적인 코드 템플릿을 익혀야 함

- 기본 코드 템플릿을 토대로 각 문제의 조건에 맞추어 답 코드를 구현

public class UnionFind {

    private static int[] parent;
    public static void main(String[] args) {
    	//문제 input 조건 따라서 N 적절히 설정
        parent = new int[N];
        
        //초기화
        for (int i = 0; i < 10; i++) {
            parent[i] = i;
        }
    }

    private static void union(int a, int b) {
        // 최상위 부모 찾기
        int x = find(a);
        int y = find(b);

        if (x < y) {
            parent[y] = x;
        } else {
            parent[x] = y;
        }
    }

    private static boolean equals(int a, int b) {
        int x = find(a);
        int y = find(b);
        return x == y;
    }

    private static int find(int a) {
        if (parent[a] == a)
            return a;
        return parent[a] = find(parent[a]);
    }
}