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

 

트리 탐색 알고리즘 - 유니온 파인드
Union Find

 

✅ 개념 / 원리

: 대표적인 트리 알고리즘 

: 합집합 찾기, 서로소 집합 알고리즘 이라고도 부른다. 

 

유니온 파인드는 집합(set)을 합하기위한 연산이다. 

양뱡향 연결 리스트를 사용해 합집합 연산 구현이 가능하지만 시작 복잡도가 안좋아 트리 형태를 활용한다. 

부모를 가르키는 트리처럼 링크를 만들어 집합을 표현한다. 

 

하나의 트리가 하나의 set이며 트리의 parents를 찾아 올라가 루트를 만나면 루트값이 집합의 대표값이다.

두개의 집합에 루트값을 찾아서(find) 루트값이 다르면 하나의 트리로 만든다.(union) 

> 트리 높이 h만큼의 시간 복잡도를 갖는다. 

 

집합의 합집합 시킨다는 개념을 생각하면 문제 풀때 헷갈려서 주어진 그래프의 루트를 찾는 알고리즘 정도로 이해하고 넘어가면 어렵지않다. 

 

✅ 구현

find

#union find - 부모노드를 찾는 함수
def getParent(x) :
    if parent[x] == x : return x
    parent[x] = getParent(parent[x])
    return parent[x]
    
#union find - 같은 부모를 가지는지 확인
def findParent(a,b) :
    a = getParent(a)
    b = getParent(b)
    if a == b : return 0 #같은 부모를 가지고있다. 즉 연결된 노드이다. 
    return 1

union

#union find - 부모 노드를 합치는 함수
def unionParent(a,b) :
    a = getParent(a)
    b = getParent(b)
    if a < b : parent[b] = a
    else : parent[a] = b
    
#연결 노드에 부모가 다르면 부모 노드를 합쳐준다    
for i in p : # p는 노드 리스트 
    if findParent(i[0],i[1]) != 0:
        unionParent(i[0],i[1])

 

❗️parent 리스트에 저장된 각 루트 노드에 다시 한번 루트 노드를 구해준다.

result = [] # 각 노드에 루트노드를 저장한다. 
for a in parent :
    result.append(getParent(a))

 이미 루트 노드로 지정된 지정된 노드의 부모 노드가 변할 경우 이미 리스트에 담긴 노드는 변경되지 않기 때문에 루트 노드를 구해야한다면 이부분을 꼭 추가해주어야한다. 

예를 들면 6의 루트노드가 3으로 변경되었는데 후에 3의 루트 노드가 1로 바뀐다면 6의 루트 노드는 3으로 남아있게된다. 

이때문에 재귀함수를 사용해야한다는 글도 봤지만 이편이 간단해서 위처럼 구현해봤다.

( 작은 노드부터 순서대로 변경되기때문에 문제 없어보이지만 반례가 있을지도 모르겠다. 백준에서는 문제없었다. )

 

 

✅ 유니온 파인드 연습문제

합집합을 시킨다는 개념이 와닿지않는다면 각 노드의 부모노드를 구하는 방식으로 이해하면된다.

 

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

1197번: 최소 스패닝 트리

1. 최소 스패닝 트리 

스패닝 트리는 모든 정점이 연결되어있으면서 사이클 없는 트리를 말한다. 때문에 n개의 정점에 n+1개의 간선을 가진다. 

최소 스패닝 트리는 kruskal알고리즘과 prim 알고리즘으로 해결 가능하다.

> kruskal알고리즘은 가중치가 작은 간선부터 하나씩 이어나가며 모든 정점을 방문하는 알고리즘이며 유니온 파인드를 이용하여 사이클의 유무를 체크한다. 

 

 

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

11724번: 연결 요소의 개수

2. 연결 요소의 개수

그래프의 정점과 간선이 주어졌을때 연결 요소의 개수를 출력하는 문제이다. 

DFS/BFS로도 구현이 가능하지만 유니온 파인드를 이용하여 연결 개수를 체크하는 방식으로 구현도 가능하다. 

 

오늘도 열코🔥