자바로 알고리즘 시작하기 7 - Disjoint Set (Union Find)

오늘은 서로 중복된 원소가 없는 '분리 집합 or 서로소 집합(Disjoint Set)'에 대해 알아보고, 이를 이용하여 노드 간의 연결 여부를 판별하는 'Union Find' 알고리즘에 대해 알아보겠습니다. 이 두 가지는 그래프 알고리즘에서 중요하게 다루어지며, 특히 최소신장트리(Minimum Spanning Tree)를 구현하는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘에서 활용됩니다.

 

먼저, Disjoint Set은 각각의 원소가 하나의 집합을 이루며, 교집합이 존재하지 않는 집합을 말합니다. 이를 연결 리스트나 트리를 통해 표현할 수 있지만, 보통 트리 구조를 사용하여 구현합니다.

 

분리 집합을 표현하기 위해 각 노드가 바라보는 부모 노드를 나타내는 parent[] 배열을 사용합니다. 초기에는 모든 노드가 각자 다른 그룹에 속해 있으므로, parent[] 배열의 각 값은 자신을 가리킵니다.

parent[1] = 1;
parent[2] = 2;
parent[3] = 3;
parent[4] = 4;
parent[5] = 5;

이제 'Union Find' 알고리즘을 통해 서로소 집합을 구현해보겠습니다. 'Union Find' 알고리즘은 크게 두 가지 연산으로 이루어집니다.

• union()
• find()

union()

'union()' 연산은 두 그룹을 하나로 합치는 작업입니다. 두 노드를 합치는 과정에서는 각 노드의 루트 노드를 찾아 더 작은 루트 노드를 기준으로 합칩니다. 이때 루트 노드를 찾는 방법은 'find()' 함수를 사용합니다.

fun union(int i, int j):
  int a = find(i);
  int b = find(j);
  if a == b: return;
  if a <  b:
    parent[b] = a;
  else:
    parent[a] = b;

find()

'find()' 연산은 해당 노드가 속한 그룹의 루트 노드를 찾는 작업입니다. 특정 노드의 루트 노드를 찾기 위해선, parent[] 배열을 계속 탐색하다가 더 이상 타고 올라갈 노드가 없을 때 그 노드를 반환하면 됩니다.

fun find(int i):
  if (parent[i] == i): // root 노드라면
    return i; // 스스로를 반환
  return find(parent(i)); // 루트 노드가 아니라면, i노드의 부모 노드로 올라가서 탐색 계속.

최적화

하지만 이 방법은 모든 노드가 연결되어있는 경우에 리프 노드부터 루트 노드까지 찾기 위해서는 O(N) 만큼의 시간이 소요되어 비효율적입니다. 이를 해결하기 위해 '경로 압축(Path Compression)' 기법을 사용하여 'find()' 함수를 최적화할 수 있습니다. 이를 통해 'Union Find' 알고리즘의 시간 복잡도는 O(log N)으로 줄일 수 있습니다.

fun find(int i):
  if parent[i] == i: // i 노드가 루트 노드라면
    return i;    // i 값을 반환합니다.

  int rootNode = find(parent[i]); // 루트 노드가 아닌 경우에는 i 노드의 루트 노드를 찾고
  parent[i] = rootNode; // parent 배열 상의 i 노드의 부모 노드를 root 노드로 갱신
  return rootNode; // 그리고나서 root 노드를 반환

 

위 코드를 더 간단하게 표현하면 아래 정도로 간소화할 수도 있습니다. (뭐를 쓸지는 취향 차이라고 생각합니다.)

fun find(int a):
  if (parent[a] == a):
    return a;
  return parent[a] = find(parent[a]);

 

대표 연습문제는 다음과 같습니다.

1717번: 집합의 표현

 

1976번: 여행 가자

 

이렇게 서로소 집합과 'Union Find' 알고리즘을 이해하면,를 활용하는 최소신장트리 알고리즘인 크루스칼 알고리즘과 프림 알고리즘을 이해하는 데 도움이 됩니다. 다음 시간에는 이 알고리즘들에 대해 자세히 알아보도록 하겠습니다. 그럼 오늘은 여기까지!