[자료구조] UnionFind 알고리즘

1일 1코딩테스트를 풀어보려고 노력하고 있습니다.

Leetcode에서 진행 중이며 금일 푼 문제에서 UnionFind 문제가 있어 정리를 해보고자 작성합니다.

 

UnionFind 알고리즘

UnionFind 알고리즘은 대표적인 그래프 알고리즘으로 서로소 집합(Disjoint-Set)알고리즘으로도 불린다.
여러개의 노드가 존재 할 때 두 노드를 선택하여 같은 그래프에 있는지 판별하는 알고리즘이다.

 

 

설명

아래와 같이 1번부터 6번까지의 노드가 있다.

 

1~6번까지의 노드들

 

 

위의 노드들은 연결 되기 전에 아래와 같이 윗칸은 노드 번호 아랫칸은 부모 노드를 뜻한다. (초기화 단계)

 

 

노드 번호	1	2	3	4	5	6
부모 노드	1	2	3	4	5	6

 

위의 노드들을 아래와 같이 2개의 그래프처럼 연결시켜 보려고 한다.

 

1~3번 노드, 4~6번 노드를 연결 한 모습

 

먼저 1, 2번 노드를 연결을 해본다. 연결을 할 때 부모는 항상 작은 값이 기준이다.

1 < 2 이기때문에 부모 노드는 1번이다.

 

노드 번호	1	2	3	4	5	6
부모 노드	1	1	3	4	5	6

 

다음으로 2, 3번 노드를 연결 해본다. 

2 < 3 이기때문에 부모 노드가 2라고 생각이 들 수 있겠지만 2번 노드의 부모노드는 위의 작업으로 인해 1번 노드라는 것을 알고 있다.(이때 재귀방식을 통해 해결한다.)

 

노드 번호	1	2	3	4	5	6
부모 노드	1	1	1	4	5	6

 

그 다음으로 4,5,6번 노드도 연결을 해준다

 

노드 번호	1	2	3	4	5	6
부모 노드	1	1	1	4	4	4

 

완성 된 표를 보면 1,2,3은 모두 부모노드가 1이고 4,5,6은 부모노드가 4이다.

 

이 방식을 소스코드로 구현해보자

 

소스 코드

[UnionFind]

public static class UnionFind {
        private int[] parent;
        
        // 초기화
        public UnionFind(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        // 부모 노드를 찾는 재귀 함수
        public int find(int n) {
            if (n == parent[n]) {
                return n;
            } else {
                return parent[n] = find(parent[n]);
            }
        }

        // 두 수를 비교하여 둘 중에 작은 수를 부모노드로 셋팅하는 함수
        public void unionAll(int a, int b) {
            int x = find(a);
            int y = find(b);

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

[Main]

예시로는 1~6번으로 하였지만 프로그램상에서는 배열이 0번부터 시작함으로 0~5로 셋팅해주었다.

public static void main(String[] args) {

    UnionFind uf = new UnionFind(6);
    uf.unionAll(0,1);
    uf.unionAll(1,2);

    uf.unionAll(3,4);
    uf.unionAll(4,5);

    uf.sameParent(0, 2);
    uf.sameParent(0, 4);
}

부모가 같습니다.
부모가 틀립니다.

Process finished with exit code 0

0,2는 부모가 같고 0,4는 부모가 다르다는 예상과 같은 결과가 나왔다.

이 알고리즘을 분석하기 좀 시간이 많이 걸렸다. 

하지만 알고나니 알아두면 유용한 알고리즘으로 보인다.

 

오늘 푼 LeetCode문제는 아래 링크이다.

LeetCode

https://leetcode.com/problems/smallest-string-with-swaps/

Smallest String With Swaps - LeetCode

 

 

오늘도 지식 + 1