유니온 파인드에서 항상 놓치는 부분은
연결하는 두 노드가 주어질 때
두 노드의 루트 노드가 같지 않다면
한쪽 노드의 루트노드의 루트노드를 다른 루트노드로 만들어야 된다는 점이다.
이걸 잊고 한쪽 노드의 루트노드만 다른 루트노드로 바꾸게 되면 그 한쪽노드에서 루트노드로 이어지는 다른 노드들이 다른쪽 루트노드를 가르키지 못하게 된다
그림으로 표현하면 아래와 같다.
<답>
초기 상황이다.
4번노드가 3번노드와 이어저 4번노드의 루트 노드가 3이되었다.
2번노드와 3번노드가 이어져 3번노드의 루트노드가 2가되었다. 여기서 4번노드는 고려할 필요가 없다. 3번노드에서 루트로 올라가는 함수를 거칠때 3번노드의 루트노드가 이미 3번이었기 때문에 재귀가 끝나기 때문이다.
이 과정이 유니온 파인드의 핵심이다. 2-3-4의 꼬리노드였던 4번노드가 루트가 다른 노드인 1번 노드와 이어질 때 4번노드의 루트노드를 1로 고치는게 아니라 4번노드는 2번노드까지 이어지는 재귀를 실행하는 과정에서 그 과정에 포함된 노드의 루트노드를 2번으로 고치기만 하고(이 과정에서 4번노드의 루트노드 3이 2로 변화고 3으로 이어진 재귀함수에서 3번 노드의 루트노드가 2로 갱신되는데 이미 2였으므로 바꾸지 않는다.) 그 루트노드인 2번 노드의 루트노드가 1로 바뀐다는 것이다.
즉 a노드와 b노드가 이어질때 b노드의 루트노드의 루트노드가 a로 갱신되어야 하는것이다. b에서 b의 루트노드로 이어지는 재귀 과정 중에 노드(여기서는 3)는 루트노드를 재확인 해주는 것이다.
다시 유니온 파인드의 과정을 설명하면
1. 이을 두 노드 a, b를 받는다.
2. a의 루트노드를 구한다. 구하는 과정에서 a 와 a의 루트 노드 사이의 노드들의 루트노드를 a의 루트노드로 재확인 및 갱신한다. 이것을 b노드에서도 마찬가지로 하여 b의 루트노드를 구한다.
3. 만약 a, b노드의 루트노드가 같다면 할 건 없지만 사이클이 있다는 뜻이기도 하다.
4. 만약 a, b노드의 루트노드가 다르다면 한 쪽 루트노드의 루트노드를 다른 쪽 루트노드로 바꿔준다.