[Python] 유니온 파인드(Union-Find)

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

해당 알고리즘이 있는 것은 알았는데 어떤 식으로 구현해서 사용하는지는 모르고 있었다.
유니온 파인드와 관련된 코테 문제들을 풀게 되었고, 이참에 유니온 파인드 알고리즘에 대해 아주 간략하게만 정리해보려 한다.

Do it! 알고리즘 코딩테스트 도서를 참고하였다.

---

📃 개념

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산
두 노드가 같은 집합에 속해 있는지 확인하는 find 연산

1차원 리스트를 사용한다.
처음엔 아무것도 연결되어 있지 않은 상태이므로 각 노드가 모두 대표 노드이다.
따라서, 자신의 인덱스값으로 초기화 해준다.

parent = [0 for _ in range(n + 1)]

for i in range(n + 1):
   parent[i] = i

이후 연결 작업은 union 연산을 통해 수행한다.
예를 들어 1과 4를 연결하게 된다면,

1. 1의 대표 노드와 4의 대표 노드를 비교한다.
2. 다르기 때문에 4의 대표노드를 1로 설정해준다.

연결 작업이 모두 끝났다면, a와 b의 대표 노드를 비교하여 같은 집합인지 확인할 수 있다.

---

🔗 유니온(union)

각 노드가 속한 집합을 1개로 합치는 연산

def union(a, b):
   a = find(a)
   b = find(b)

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

1. a와 b의 대표 노드(부모 노드)를 찾고 비교한다. // 찾을 때는 find 연산
2. 다르다면, b의 대표 노드를 a의 대표 노드로 변경한다.

---

🔎 파인드(find)

특정 노드 a에 관해, a가 속한 집합의 대표 노드를 반환하는 연산

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

1. 대상 노드 리스트의 index 값과 value 값이 동일한지 확인한다.
2. 다르다면 value 값이 가리키는 index 위치로 이동한다.
3. 이동 위치의 index 값과 value 값이 같을 때까지 1 ~ 2를 반복한다. (재귀 함수)
4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 대표 노드 값으로 변경한다.

---

✅ 체크 함수

두 원소가 같은 집합에 속해 있는지 확인하는 함수

def checkSameSet(a, b):
   a = find(a)
   b = find(b)

   if a == b:
      return True
   else:
      return False