[Algorithm] Union - Find (Python 구현)

유니온 파인드 파이썬 구현하기 / union - find by Phython

유니온 / 파인드는 현재 노드들이 같은 그룹에 속해 있는지 확인하고 같은 그룹으로 만드는 병합이 필요할 때 사용하는 알고리즘입니다.

find 알고리즘 구현

par = [ -1 for i in range(N + 1) ]  # 루트를 담을 배열

def find(x):    # 루트를 찾아주는 함수
    if par[x] < 0:  # 아직 루트가 없다면
        return x    # 자기 자신이 루트  => 아직 연결된 적이 없음
    par[x] = find(par[x])   # 자신의 부모를 부모->부모 를 재귀로 루트 부모를 찾음
    return par[x]   # 루트 부모를 리턴

par 이라는 배열에는 각 노드의 부모를 담아 놓습니다.

par 배열의 index는 각 노드의 번호이고 그 값은 부모 노드를 의미합니다.

 

처음 모든 노드의 값을 -1(아직 부모가 정해지지 않음)으로 초기화합니다. -> 모든 노드(index)는 아직 부모 노드가 없음(-1)

 

find 함수는 재귀적으로 자신의 부모의 부모를 탐색합니다. 최종적으로 부모가 없는 노드(값이 -1인 노드)를 발견한다면 최상위 노드(root)로 볼 수 있습니다.

최상위 노드를 찾았다면 해당 노드의 값을 리턴하고 그 이전의 노드들은 최상위 노드의 번호로 자신의 부모 노드를 갱신하게 됩니다.

union 알고리즘 구현

def union(a, b):    # union 두 집합을 연결해주는 함수
    a, b = find(a), find(b) 
    if a == b:  # 루트 부모가 같다면 같은 집합 => 이미 연결 관계
        return False
    par[b] = a  # 부모 노드를 통일시켜 하나의 집합으로 병합
    return True

union 혹은 merge 알고리즘은 두 노드를 인자로 받아서 해당 노드들이 같은 그룹인지 확인하는 알고리즘입니다.

find 함수를 통해서 해당 노드의 부모 노드를 확인합니다.

위 함수에서는 인자로 받은 a, b변수에 부모의 노드의 값을 대입해 주었습니다. (인자로 받은 값은 지역변수 이므로 원본 a, b 가 변하지는 않습니다.)

 

만약 부모의 값이 같다면 같은 이미 같은 그룹이기에 'False'를 리턴하여 함수를 종료합니다.

그렇지 않다면, 다른 노드이므로 병합을 위해서 한쪽의 부모 노드를 다른 노드의 부모 노드로 갱신합니다. (어느 것이든 상관없습니다.)

갱신 후 같은 갱신을 하였다는 의미로 'True'를 리턴합니다.

 

union 함수의 목적은 두 부모 노드를 동일하게 만들어 하나의 그룹임을 확인할 수 있는 상태로 만드는 것에 있습니다. 따라서 return 값의 경우 필요에 따라서 수정할 수 있습니다.