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

Union Find

- 유니온 파인드

- 그래프 자료구조에서 주로 사용하는 알고리즘

- 두 노드가 같은 그래프에 속하는지 판별

- 서로소 집합(Disjoin-Set)으로도 불린다.

- 노드를 합치는 Uion 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.

- 트리 구조로 이루어진 자료구조 중 한 가지로 생각되기도 한다.

 

 

그래프에서 임의의 두 정점이 연결 그래프인지 확인하고 싶다면 그래프를 순회하며 두 정점이 연결 되어 있는지 확인해 볼 수도 있지만 많은 정점에 대해서 동일한 작업을 반복하면 오랜 시간이 걸릴 것이다. 그러나 그래프의 일부분을 일종의 트리로 보고 공통의 루트 노드를 같는 노드끼리 하나의 집합으로 본다면, 두 노드에 대한 부모 노드의 동일 여부만 알아도 그래프의 모든 정점을 순회하지 않고도 두 정점이 연결되어 있는지 알 수 있게 된다.

 

public int find (int x) {
    if (parent[x] == x) return x; // 현재 노드의 부모가 존재하지 않는경우(현재 노드가 루트노드) 자기 자신 반환
    return parent[x] = find(parent[x]); // 현재 노드의 부모 노드가 존재한다면 재귀를 통해 루트노드를 찾아 반환
}

// 부모 노드(루트 노드) 가 같다면 두 노드의 부모 노드를 같게 만든다. 
public void union (int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return; // x와 y의 부모 노드가 같다면 두 노드는 연결되어 있다.
    
    // 부모 노드와 같게 만드는 union 작업
    
    // 더 작은(우선순위가 높은) 노드를 부모 노드로 선정한다. 
    if (x < y) 
    	parent[y] = x; 
    else 
    	parent[x] = y;
}

 

 

 

 

 

 

 

 

 

위 그림을 보면 노란색과 주황색 두 그룹이 있다. 부모 노드 개념을 적용하여 이제는 부모 노드를 따라 올라가면 같은 그룹인지 아닌지 확인할 수 있다. 그런데 주황색 그룹을 보면 자식 노드가 루트 노드인 3번의 한쪽 방향으로 쏠려있다.

이렇게 자식 노드가 한쪽 방향으로 모여있는 경우 find 연산으로 루트 노드를 찾아갈 경우 탐색하는데 시간이 오래 걸릴 수도 있다. 예로 2번 노드는 부모 노드를 찾기 위해 find연산을 한번만 사용하면 되지만, 6번 노드의 경우 부모 노드를 찾아가려면 find 연산을 3번 사용해야 루트 노드인 3까지 도달할 수 있다. 

 

 

 

 

이 경우 find 연산을 할 때, 매개변수로 들어온 현재 노드 num이 루트 노드가 아닌 경우 parent[num]  = find(num)을 통해 루트 노드를 부모 노드로 최신화 시키는 작업을 추가하면 부모-자식 노드 간의 관계가 아래 그림처럼 바뀐다.

public int find (int num) {
	if (parent[num] == num) return num;
    return parent[num] = find(parent[num]); // 부모 노드를 최신화
}

 

 

.

 

위 트리는 부모노드 관계를 표현한 것일 뿐 처음에 주어진 그래프모양은 변하지 않는다. 부모 관계 트리에서 노드와 부모 노드간의 관계가 위와 같이 재정비되면, 이 다음 부모 노드를 찾는데 필요한 find 연산의 횟수가 줄어든다.

 

추가로 union 연산시 노드간에 우선순위를 부여하여 일관성 있게 부모 노드를 설정하면 성능이 더 좋아진다. 

 

 

 

 

유니온 파인드 관련 문제

 

[백준] 1717번 - 집합의 표현

 

[백준] 1976번 - 여행 가자