Day-15 유니온 파인드

---

1. Union, Find 연산

• 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산
  노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B이다.
• 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산
  노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다.

위 두 연산으로 구성되어 있는 알고리즘이 유니온 파인드이다.

---

2. 유니온 구현

1차원 배열을 이용하여 유니온 파인드를 표현한다.

처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다.

 

2개의 노드를 선택해 union 연산을 수행한다.

union(1, 4)의 경우, 4번 노드의 대표 노드를 1번 노드로 하여 연결한다.

union(4, 6)의 경우, 6번 노드와 4번 노드의 대표 노드가 각각 5번, 1번 노드이므로 5번 노드의 대표 노드를 1번 노드로 하여 연결한다.

---

3. 파인드 구현

1. 대상 노드 배열에 index값과 value값이 같은지 확인
2. 같지 않으면 value값이 가리키는 index 위치로 이동
3. 이동 위치의 index값과 value값이 같을 때까지 과정 1, 2를 반복
4. 대표 노드에 도달하면 거치는 모든 노드값을 루트 노드값으로 변경

find 연산을 사용하면 경로 압축의 효과가 나타나, 시간 복잡도가 줄어드는 효과를 얻는다.

이렇게 되면 추후 노드와 관련된 find 연산 속도가 O(1)로 변경된다.

---

4. 예제 문제

---

[20040] 사이클 게임 (JAVA)