알고리즘 공부

손승열(Son Seungyeol)

2023년 6월 22일

유니온 파인드(Union-Find)

유니온 파인드 알고리즘에 대해 공부해봅니다.

업데이트됨: 2023년 6월 22일 오전 02:25

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

유니온 파인드는 그래프 알고리즘 중 하나로 두 노드 A와 B가 있을 때 A와 B가 같은 그래프에 속하는 지를 판단하는 알고리즘입니다. 서로소 집합, 분리 집합 또는 상호 배타적 집합(Disjoint-set)이라고도 불립니다.

무엇을 할 수 있나?

유니온 파인드 알고리즘을 익히고 난다면 다음과 같은 일들을 해낼 수 있습니다.

[기본] 두 노드가 같은 그래프에 속해 있는 지 판단
[응용] 그래프가 회로(사이클)을 형성하는 지 판단
[응용] 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘(Kruskal Algorithm)에 활용

어떻게 구현할 수 있나?

유니온 파인드 알고리즘은 다른 이름인 "분리 집합"에서도 알 수 있듯이 서로 연결되지 않은 각각의 그래프를 "분리"하여 표현함으로써 추후 두 노드가 같은 그래프를 구성하는 지를 알 수 있습니다. 각각의 분리된 그래프(집합)는 그래프를 대표하는 노드로 표현할 수 있는데, 배열을 통해 이를 구현할 수 있습니다. 또한 유니온 파인드 알고리즘은 크게 아래의 두 부분으로 나누어 구현합니다.

유니온: 임의의 두 노드 A와 B를 같은 그래프(집합)에 포함시킵니다.
파인드: 임의의 노드 A가 속한 그래프(집합)의 대표 노드를 찾습니다.

알고리즘의 흐름은 다음과 같습니다.

대표 노드를 나타내는 배열의 값을 자기 자신(인덱스 = 값)으로 초기화합니다.
동일한 그래프에 포함시키고자 하는 임의의 두 노드 A와 B에 대해 각각 위의 파인드 연산을 거쳐 각각의 노드가 속한 그래프의 대표 노드를 찾습니다. (초기의 경우 각각 A와 B)
대표 노드가 같은 경우는 이미 동일한 그래프에 포함되어 있는 것이므로 별다른 연산을 하지 않습니다.
대표 노드가 다른 경우에는 유니온 연산을 통해 두 노드가 속한 그래프의 대표 노드를 동일한 값으로 바꿉니다.

트리의 치우침 문제 해결

간혹 별다른 처리 없이 유니온 파인드 알고리즘을 작동시키면 아래와 같이 트리가 형성될 수 있습니다.

A
 \
  B
   \
    C
     \
      ...

이렇게 트리의 치우침 문제가 발생하는 경우 추후 대표 노드의 탐색 연산 등에서 알고리즘의 효율이 저하될 수 있습니다. 따라서 이를 해결하기 위해서 간단한 규칙을 추가합니다. 노드들을 정수로 표현할 때, 대표 노드는 그 그래프(집합)를 구성하는 노드 중 가장 작은 값의 노드로 하는 것입니다.

   1      5
 / | \    |
2  3  4   6

이러한 규칙을 토대로 유니온 연산과 파인드 연산을 수행할 때 부모 노드(대표 노드)를 지속적으로 갱신하며 트리의 치우침 문제를 해결할 수 있습니다. (자세한 내용은 아래의 코드를 참조해주세요.)

그래프의 회로(사이클) 형성 판단

유니온 파인드 알고리즘을 사용하면 어떠한 그래프가 회로(사이클)을 형성하는 지 쉽게 파악할 수 있습니다. 예를 들어 다음과 같은 그래프가 있다고 가정해봅시다.

위와 같이 그래프가 회로를 형성할 때 다음과 같은 과정을 통해 회로의 존재 여부를 파악할 수 있습니다.

노드1과 노드2를 union ➡️ 서로 대표 노드가 다르므로(각각 노드1, 노드2) union 가능
노드1과 노드3을 union ➡️ 서로 대표 노드가 다르므로(각각 노드1, 노드3) union 가능
노드2와 노드4를 union ➡️ 서로 대표 노드가 다르므로(각각 노드1, 노드4) union 가능
노드3과 노드4를 union ➡️ 두 노드의 대표 노드가 같으므로(각각 노드1, 노드1) 사이클 발생!

⌨️ C++ 구현 코드

cpp

#include <bits/stdc++.h>
#define MAXN 100

using namespace std;

int parents[MAXN];

int find_parents(int x){
  if(parents[x] == x) return x;

  //부모 노드를 갱신하면서 찾기
  return parents[x] = find_parents(parents[x]);
}

void union_nodes(int a, int b){
  a = find_parents(a);
  b = find_parents(b);

  //두 노드의 부모(대표) 노드가 같다면 이미 한 그룹
  if(a == b) return;

  if(a < b) parents[b] = a;
  else parents[a] = b;
}

int main()
{
  //초기화 - 나의 부모 노드를 자기 자신으로 설정
  for(int i=0;i<MAXN;i++) parents[i] = i;

  union_nodes(2, 3);
  union_nodes(2, 4);
  union_nodes(3, 5);
  union_nodes(6, 7);
  union_nodes(1, 2);

  //추가적인 작업(필요에 따라) - 대표 노드 갱신해주기
  //ex) 3, 4노드의 대표 노드가 2였는데, 2노드의 대표 노드가 1노드가 된 경우
  //    (2, 3, 4) -> (1, 2, 3, 4)
  //    3, 4노드의 대표 노드를 1로 바꿔주는 방식
  for(int i=0;i<MAXN;i++) parents[i] = find_parents(i);
}