[그래프] 유니온-파인드(Union-Find)

🍀 목차
유니온-파인드 알고리즘
기본 이해
구현(JavaScript)
활용 예
시간 복잡도

유니온-파인드 알고리즘

• 집합을 관리하는 자료구조 유니온-파인드를 활용해 합집합을 찾는 알고리즘이며, Disjoint Set(서로소 집합, 상호 배타적 집합), Merge find Set 알고리즘이라고도 불린다. 
• 유니온-파인드는 루트 노드 밑에 자식 노드들이 엮인 트리 구조를 따른다. 
• 여러 개의 노드 중 선택된 두 노드가 같은 그래프에 속해 있는지 판별한다.
• 크게 3가지의 과정을 거친다.
  1. Initialization(초기화) : 각 노드가 각각의 집합에 포함되도록 초기화하는 과정
  2. Find(찾기) : 특정 노드의 부모를 찾는다. (해당 노드가 속한 집합의 루트를 반환한다.)
  3. Union(합치기) : 두 노드 A와 B를 한쪽으로 합친다. (노드 번호가 작은 쪽 or 큰 쪽 or 트리 높이가 낮은 쪽)

기본 이해

원숭이마을

 여러 원숭이가 사는 마을이 있다. 이 마을에는 두 마리의 대장 원숭이가 있다. 이 마을에 이사를 오려면 입국 심사를 거친 후 두 대장 원숭이 중 한 원숭이 밑으로 들어가야 한다. 그러므로 지나가는 일반 원숭이에게 인터뷰를 요청하면 당연히 그 원숭이는 두 대왕 중 한 마리의 이름을 댈 것이다. 두 마리의 일반 원숭이에게 인터뷰를 요청했을 때 대장 원숭이가 누군지 물어보면 두 원숭이가 같은 파인지 아닌지 알 수 있을 것이다. 

 

 유니온-파인드 알고리즘은 입국 심사 전 자기 자신에게 속해있던(초기화 과정) 원숭이들이 대왕 밑으로 들어가고(Union 과정) 나중에 인터뷰를 요청했을 때 대왕 원숭이 이름을 대서(Find 과정) 어디 파 인지 확인하는 과정이라고 생각할 수 있다.

 

 응용해 보면 많은 대장 원숭이가 있는 마을에서 몇 개의 원숭이 파가 있는지 궁금하다면 일반 원숭이들에게 인터뷰를 요청해 나온 대장 원숭이 이름들을 세본다면 해당 마을의 원숭이 파 수를 알 수 있다.

 유니온-파인드 알고리즘을 통해 각 집합이 서로 공통 원소를 갖지 않는 Disjoint Set(상호 배타적 집합)이 구해진다.

 

구현(JavaScript)

1. 초기화 과정 : 자기 자신에게 속해 있는 과정(입국 심사 전)

const init = (N) => { //N개의 노드
  return Array(N)
    .fill(0)
    .map((value, idx) => idx);
};

 

2. Find 과정 : parent라는 배열이 있고 Union 과정이 다 진행된 후, 👉 parent[i] === i 라면 그 원숭이가 대장일 것이다. (인터뷰 시 자기 자신의 이름을 말하는 원숭이)

 

계층으로 구현한다면.

 만약 서열까지 있는 마을이라면 병사 원숭이는 부대장 원숭이를, 부대장 원숭이는 대장 원숭이 이름을 댈 것이다. 하지만 유니온-파인드라는 관점에서 봤을 때 결국 우리가 구해야 할 것은 상호 배타적 집합이다. 이러한 대장👈 부대장 👈 병사의 구조를 갖게 된다면 극단적으로 100개의 서열이 있는 마을의 경우 최말단의 원숭이의 부모 노드를 찾으려면 100번 Find 해야 한다. 편향 트리로 구현한다면 시간 복잡도가 매번 O(N) 걸린다는 것이다.

const find = (x, parent) => { //O(N)
  if (parent[x] === x) {
    return x;
  } else {
    return find(parent[x], parent);
  }
};

 결국 계층이 생겼더라도 모든 노드는 루트 노드 밑에 속해 있으니 부모 노드를 찾았다면 해당 노드에 기록된 값을 부모 노드로 바꿔준다면 효율을 높일 수 있다. 이를 경로 압축(Path compression)이라고 하며, 평균 시간 복잡도는 O(logN)이 된다.

 

경로 압축.

const find = (x, parent) => {
  if (parent[x] === x) {
    return x;
  }
  const currentParent = find(parent[x], parent);
  parent[x] = currentParent;

  return currentParent;
};

 

3. Union 과정 : 두 노드가 포함된 집합을 합친다. 대장 원숭이일수록 노드 번호가 작다는 전제 하에, 두 집합을 합칠 때 부모 번호가 더 작은 집합 밑으로 부모 번호가 큰 집합을 합치기로 하자.

const union = (A, B, parent) => {
  const rootA = find(A, parent);
  const rootB = find(B, parent);

  rootA < rootB ? (parent[rootB] = rootA) : (parent[rootA] = rootB);
};

최종 코드

const init = (N) => {
  return Array(N)
    .fill(0)
    .map((value, idx) => idx);
};

const find = (x, parent) => {
  if (parent[x] === x) {
    return x;
  }
  const currentParent = find(parent[x], parent);
  parent[x] = currentParent;

  return currentParent;
};

const union = (A, B, parent) => {
  const rootA = find(A, parent);
  const rootB = find(B, parent);

  rootA < rootB ? (parent[rootB] = rootA) : (parent[rootA] = rootB);
};

 

 

✨ 더 개선시킬 수 있는 방법

 

 계층 구조가 깊은 두 집합을 합칠 때, 트리의 깊이가 더 낮은 트리가 높은 트리 밑으로 들어가야 효율적이다. 그래서 높이를 기록하는 배열을 추가하여 Union 시마다 갱신, 더 낮은 높이의 트리를 높은 트리에 Union 한다(Union by Rank). 하지만 이 방법도 높이를 기록하는 배열을 추가한다는 단점이 있고, 이를 개선하고자 Weighted Union Find라는 방법이 고안되었다. parent 배열에서 탐색했을 때 음수라면, 부모노드이고 그 절댓값이 해당 트리의 높이가 되고 양수라면, 부모 노드를 가리키게 된다. parent[2]가 -3이라면 2번 노드는 부모 노드로서 트리의 높이가 3이 되는 것이고, 5라면 2번 노드의 부모가 5번 노드라는 뜻이 된다. 

 이렇게 개선할 경우, 초기화 과정을 -1로 해줘야 하고(부모 노드로서 높이가 1인 트리), Find 과정도 음수와 양수로 구분을 해주는 등의 조금의 수정이 필요하다. 최종 코드는 아래와 같다.  문제에 따라 더 이해하기 쉬운 코드를 사용하면 될 것 같다.

const init = (N) => {
  return Array(N).fill(-1);
};

const find = (x, parent) => {
  if (parent[x] < 0) {
    return x;
  }
  const currentParent = find(parent[x], parent);
  parent[x] = currentParent;

  return currentParent;
};

const union = (A, B, parent) => {
  const rootA = find(A, parent);
  const rootB = find(B, parent);

  if (rootA === rootB) {
    return;
  }

  if (parent[rootA] < parent[rootB]) {
    //둘 다 음수이므로, 더 작은 값이 높이가 더 큰 트리이다.
    parent[rootA] += parent[rootB];
    parent[rootB] = rootA;
  } else {
    parent[rootB] += parent[rootA];
    parent[rootA] = rootB;
  }
};

 

활용 예

 그래프 문제에서 사이클이 존재하는지 확인할 때 사용된다. 

MST 알고리즘 중 크루스칼 알고리즘에서도 트리를 확장할 때 사이클이 발생하는지 확인할 때 사용할 수 있다. 그래프를 연결하려고 할 때 두 노드의 루트 노드가 같다면 이어져있다는 것이 되는데, 이 두 노드를 연결하게 되면 닫힌 그래프인 사이클이 생긴다는 것. 

 

시간 복잡도

$$O(α(N))$$

 

 유니온-파인드 알고리즘의 시간 복잡도는 최적화 여부와 순서 등에 따라 달라진다고 한다. 결국 Find 함수를 어떻게 구현하느냐에 따라 복잡도가 달라진다. 편향 트리로 구현을 한다면 O(N), 경로 압축을 할 경우는 O(logN)으로 생각할 수 있다. 

 

  Union by Rank와 Path compression이 모두 적용된 경우, 평균 시간 복잡도는 α(N)라고 한다. 

α(N) : 애커만(Ackermann) 함수를 의미하며 N이 2^65536일 때ㅡ 5가 된다. 상수 시간 복잡도로 생각해도 된다.

 

---

참고 자료

https://ssungkang.tistory.com/198