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

유니온 파인드 알고리즘 이란?

그래프 알고리즘에 속하는 유니온 파인드는 주로 두 개의 노드를 선택했을 때 이 노드들이 같은 집합인지를 알아내는 알고리즘으로 '합집합 찾기'라고도 부른다. 

두 개의 노드를 하나로 합치는 유니온(Union)과 선택한 노드가 어느 집합에 있는지 확인하는 파인드(Find)를 합쳐 유니온 파인드 알고리즘이라고 부른다.

 

유니온 파인드 과정

1. 노드의 배열을 인덱스 자기자신으로 초기화 한다.

parent = [i for i in range(n+1)]

2. Find 함수 만들기

Find 함수는 노드 x의 부모노드 즉, 노드 x가 포함된 집합의 루트 노드를 찾는 함수이다.

def find(x):
	# 만약 x의 부모가 자기자신이 아니라면 재귀를 통해 루트 노드를 찾는다.
    if parent[x] != x:
        return find(parent[x])
    # 자기자신이라면 본인이 루트노드인 경우이므로 그대로 출력한다.
    return parent[x]

3. Union 함수 만들기

Union함수는 노드 a와 b를 합치는 함수로 둘 중 원소 값이 작은 노드를 그 집합의 루트노드로 정한다.

def union(a,b):
	# a와 b의 루트노드 찾기
    a = find(a)
    b = find(b)
    # 둘 중 원소 값이 작은 원소를 루트노드로 정하여 저장한다.
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

 

그러면 주어진 그래프로 유니온 파인드를 실행해보자

 

위 그림 같은 그래프가 있다고 생각해보자

이 그래프는 1-2, 1-4, 4-5, 3-6의 관계를 가진 그래프로 이 관계를 입력받아 유니온(Union) 해보자

그럴 경우 아래와 같은 과정을 거쳐 부모 그래프가 완성된다.

1번노드와 2번노드를 유니온 하면 1번과 2번 중 1번이 더 작은 수 이므로 배열의 2번을 1로 변경한다.

1번노드와 4번노드를 유니온 하면 1번과 4번 중 1번이 더 작은 수 이므로 배열의 4번을 1로 변경한다.

4번노드와 5번노드를 유니온 하면 4번과 5번 중 4번이 더 작은 수 이므로 배열의 5번을 4로 변경한다.

3번노드와 6번노드를 유니온 하면 3번과 6번 중 3번이 더 작은 수 이므로 배열의 6번을 3으로 변경한다.

 

이렇게 그래프의 모든 관계의 유니온이 완료되어 부모 배열이 완성되었다.

위 배열을 보면 1, 2, 4번이 같은 집합이고 3, 6번이 같은 집합임을 알 수 있다.

5번 노드의 부모는 4번으로 되어있지만 4번의 부모는 1번이고 1번은 자기자신이 부모이므로 5번도 1, 2, 4번과 함께 같은 집합인 것이다.

 

 

마지막으로 위 코드를 최적화시켜 시간을 줄여보자.

부모 관계를 매번 찾아야 한다면 시간이 더 많이 걸린다.

따라서 부모를 찾아서 리턴하는 것이 아니라 저장한다면 루트노드가 저장되어 다음에 똑같은 노드의 부모를 찾을 때 이미 배열에 저장된 루트노드를 사용할 수 있어 시간을 절약할 수 있다.

def find(x):
    if parent[x] != x:
        # 시간을 줄이기 위해 부모를 찾음과 동시에 저장한다.       
        parent[x] = find(parent[x])
    return parent[x]

 

아래는 유니온 파인드를 사용한 대표적인 백준 문제를 풀이한 링크이다.

[백준 1717번] 집합의 표현 - 파이썬(python)