[알고리즘] Java로 구현한 Union-find

Union-find에는 2가지 연산 존재(Union, Find)

---

0. 초기 그룹 상태 초기화

- 초기 그룹은 자기 자신을 가리키도록 설정해주어야 함. (각각이 개별 그룹)

public void init(int[] parent) {
    for(int i = 0; i<parent.length; i++)
        parent[i] = i;
}

1. 자기가 속한 그룹의 대표값 (find)

- 1, 2, 3, 4, 5가 한 그룹일때 5->4, 4->3, 3->2, 2->1 이런 식으로 가리키도록 구현하면 효율이 좋지 않음.

- 5->1, 4->1, 3->1, 2->1 이런식으로 가리키도록 구현

public int find(int[] parent, int a) {
  int temp = a;
  if (parent[temp] != temp)
      parent[temp] = find(parent, parent[a]);

  return a;
}

2. 그룹 간 결합 함수 (union)

- 각 그룹의 부모노드를 찾은 후, 한쪽의 부모노드를 다른쪽의 부모노드로 바꿈.

- 나중에 find 다시 호출 시 일괄적으로 변경됨.

public void union(int[] parent, int a, int b) {
    int t = find(parent, a);
    int l = find(parent, b);

    if (t != l) {
        parent[t] = l;
    } 
}