[Algorithm] 유니온 파인드(Union-Find) 알고리즘 (python)

유니온 파인드 알고리즘

유니온 파인드 알고리즘은 이름 그대로 유니온 연산과 파인드 연산으로 구성되어 있는 알고리즘이다.

그래프에서 두 노드가 같은 그래프에 속해 있는지를 확인할 수 있다.

 

1. union 연산

두 노드가 속한 집합을 하나의 집합으로 합치는 연산이다. 

 

2. find 연산

특정 노드가 속한 집합의 대표 노드를 반환하는 연산이다.

 

 

 

파이썬으로 유니온 파인드 알고리즘 구현하기

 

1. 1차원 리스트 사용

인덱스를 노드라고 생각하고 대표 노드 값을 리스트의 값으로 본다.

 

2. 2개의 노드의 집합을 하나로 합치는  union 연산 진행

 

두 노드를 합칠 때 두 노드의 리스트 값이 대표 노드가 아닌 경우가 있을 수 있다.

그럴 때 각 노드의 대표노드를 찾아서 대표 노드끼리 연결을 해야 한다.

3의 대표 노드가 1이고 5의 대표 노드가 4인 경우 union(3, 5)를 연결해보자.

 

3의 대표노드가 1, 5의 대표 노드가 4인 상황

그러면 3의 대표 노드인 1과 5의 대표 노드인 4를 연결해야 한다.

따라서 다음과 같은 결과가 나온다.

 

3의 대표노드 1과 5의 대표 노드인 4를 연결

 

3. find 연산으로 각 노드의 대표 노드를 찾는다.

find 연산을 진행하면서 거치는 노드 값을 대표 노드 값으로 변경한다.

 

 

 

유니온 파인드 알고리즘을 활용한 문제

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

1717번: 집합의 표현

 

 

참고한 책 : Do it! 알고리즘 코딩테스트 파이썬편