유니온파인드 알고리즘

유니온 파인드란?

유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘

• Union 연산 : 노드를 합친다. (루트 노드가 더 작은 노드로)
• Find 연산 : 노드의 루트노드 찾는다.

Union - Find 과정

1. parent [] 루트 노드를 가리키는 리스트 만들어 각 노드가 자신을 가리키도록 초기화

2. union(1,2) 연산 -> 1과 2의 루트 노드를 찾는다.

합칠 때는 루트 노드가 더 작은 쪽으로 합치며 노드 1이 루트 노드가 더 작기 때문에 

parent 리스트에서 2의 루트 노드를 노드 1의 루트노드 1로 바꿔준다.

# union find 알고리즘

# find 연산 : 루트 노드 찾기
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

# union 연산 : 더 작은 루트 노드로 합치기
def union(x,y):
    x = find(x)
    y = find(y)
    if x<y:
        parent[y] = x
    else:
        parent[x] = y
parent = list(range(9))
union(1,2)
print(parent)
union(2,3)
print(parent)
union(4,5)
print(parent)
union(4,6)
print(parent)
union(6,7)
print(parent)

 

관련 문제

백준 1197번

https://www.acmicpc.net/problem/1197

import sys
input = sys.stdin.readline
from queue import PriorityQueue
sys.setrecursionlimit(1000000)
v, e = map(int, input().split())

pq = PriorityQueue() # 우선순위큐
# 루트노드 초기화
parent = [0] * (v+1)
for i in range(v+1):
    parent[i] = i

for i in range(e):
    a,b,c = map(int, input().split())
    pq.put((c,a,b)) # 가중치 우선으로 우선순위 큐에 삽입
# print(pq.queue) # 우선순위 큐 출력

def find(x):
    if parent[x] != x:
         parent[x] = find(parent[x])
    return parent[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if x<y:
        parent[y] = x
    else:
        parent[x] = y

useEdge = 0
result = 0
while useEdge < v-1:
    w,s,e = pq.get()
    # print(w,s,e)
    # 루트 노드가 같을 때까지 가중치 더하기
    if find(s) != find(e):
        union(s,e)
        useEdge += 1
        result += w
print(result)