[알고리즘] 유니온 파인드

김제현·2023년 5월 13일

알고리즘

목록 보기

4/17

2023. 05. 12.

유니온 파인드 (Union-Find) 📌

일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find 연산(자신의 대표 노드를 찾아줌)으로 구성되어 있는 알고리즘이다.

유니온파인드의 핵심 이론

📢 유니온파인드의 원리

유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화한다.
2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다. 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합치게 된다. (union 연산은 항상 대표노드끼리 연결)
ex) union(1,4) => 4의 부모를 1로, union(5,6) => 6의 부모를 4로 설정한다.
다음으로 union(4,6)을 가정하자. 노드 4와 노드 6은 대표 노드가 아니므로 각 노드의 대표노드를 찾아 올라간 다음 그 대표 노드를 연결해야 한다. 아래 사진과 같이 노드 4의 대표노드 노드 1과 노드 6의 대표노드 노드 5를 연결한 것이다. 그렇게 되면 리스트는 [1,2,3,1,1,5] 가 된다.
find 연산은 자신이 속한 집합의 대표 노드를 찾는 연산이다. find 연산은 단순히 대표 노드를 찾는 역할만 하는 것이 아니라 그래프를 정돈하고 시간복잡도를 줄인다.
find 연산의 작동 원리
- 대상 노드 리스트에 index값과 value값이 동일한 지 확인
- 동일하지 않으면 value값이 가리키는 index 위치로 이동
- 대표 노드를 찾을 때까지 위 과정을 반복하며 재귀 함수로 구현
- 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경
```
def find(a): # find 연산
	if a == parent[a]:
    	return a
    else:
    	parent[a] = find(parent[a]) # 경로 압축 -> 재귀 함수로 구현
        return parent[a]
```

실행 코드

부모 노드를 찾는 함수

#include <stdio.h>

int getParent(int parent[], int x) {
	if(parent[x] == x) return x;
    return parent[x] = getParent(parent, parent[x])

두 부모 노드를 합치는 함수

int unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
    b = getParent(parent, b);
    
    if (a < b) parent[b] = a
    else parent[a] = b

같은 부모를 가지는 지 확인

int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
    b = getParent(parent, b);
    
    if(a==b) return 1;
    return 0;

2023. 05. 12. 오늘의 문제풀이 ✍

BOJ 1717 - 집합의 표현

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,m = map(int,input().split())

parent = [0] * (n+1)

def make_set(a):
    parent[a] = a

for i in range(1,n+1):
    make_set(i)

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]
    
def union(a,b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[b] = a

for _ in range(m):
    data, a, b = map(int,input().split())

    if data == 0:
        union(a,b)
    else:
        if find(a) == find(b):
            print("YES")
        else:
            print("NO")

#### union by rank 
'''
def make_set(a):
    parent[a] = a
    rank[a] = 0

for i in range(1,n+1):
    make_set(i)

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]
    
def union(a,b):
    a = find(a)
    b = find(b)

    if a != b:
        if rank[a] < rank[b]:
            parent[a] = b
        else:
            parent[b] = a
            if rank[a] == rank[b]:
                rank[a] += 1

'''

BOJ 1922 - 네트워크 연결

import sys

input = sys.stdin.readline

n = int(input())
m = int(input())
data = []
parent = [i for i in range(n+1)]
result = 0

for _ in range(m):
    a,b,c = map(int,input().split())
    data.append((a,b,c))

data.sort(key = lambda x : x[2])

def find(a):
    if a == parent[a]:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]
    
def union(a,b):
    a = find(a)
    b = find(b)

    if a != b:
        parent[b] = a
        
for a, b, c in data:
    if find(a) != find(b):
        union(a,b)
        result += c

print(result)