[코딩 테스트] Union Find

Union Find

두 노드가 같은 집합에 속하는지 판별하는 알고리즘이다.
합집합 찾기 알고리즘이라고도 부르며, 역으로 서로 연결되어 있지 않은 노드를 판별할 수도 있기 때문에 서로소 집합 (Disjoint-set)이라고도 부른다.

BOJ16562 친구비 문제(https://www.acmicpc.net/problem/16562)를 접하면서 처음으로 알게되었다.
1번 친구가 2번과 친구이고, 2번이 1번과 친구이고, 3번이 4번과 친구이고, 4번이 5번 친구일 경우 최소의 친구비용을 구하는 문제다.

친구인 그룹끼리 합집합으로 나타낼 수 있고, 그 중 부모노드를 설정할 수 있다. 그 기준은 친구비용이 가장 적은 사람으로 둔다.

1번 친구가 비용이 작으므로 {1, 2} 중 2번의 부모 노드는 1번
3번 친구가 비용이 작으므로 {3, 4, 5} 중 4번과 5번의 부모 노드는 3번

다음 두 가지 함수를 이용해 유니온 파인드를 만들자.

그 전에 친구 비용과, 부모노드를 미리 설정해두자.

friend_fee = [0] + list(map(int, input().split()))
parent = [x for x in range(N + 1)]

ex) 친구가 5명일 때, 1번째 친구부터 시작할 경우 (앞에 0번째는 0으로 선언한다.)
frined_fee = [0, 10, 10, 20, 20, 30]
parent = [0, 1, 2, 3, 4, 5]

1> union (서로 다른 두 트리(집합)를 합치는 연산)
union 연산은 두 원소의 부모 노드를 찾고 번호가 큰 노드가 번호가 작은 노드의 부모를 가리키도록 한다.

def find(target): # 특정 노드의 부모를 찾는다. 
    if target == parent[target]:
        return target
    # find 함수 부분을 '경로 압축' (Path Compression) 을 통해 다음과 같이 리팩토링 할 수 있다.
    parent[target] = find(parent[target])
    return parent[target]

2> find (루트 노드를 찾는 연산)

def union(a, b): # 두 노드 중 부모노드를 설정한다.
    a = find(a)
    b = find(b)
    if a != b:
        if friend_fee[a] <= friend_fee[b]:
            parent[b] = a
        else:
            parent[a] = b

for i in range(M): # v와 w의 노드를 입력받아 친구비 기준으로 union() 시킨다.
    v, w = map(int, input().split())
    union(v, w)