두 집합이 서로소(Disjoint Set)인지 확인하는 방법

서로소 집합(Disjoint Set)이란?

두 집합이 서로소(disjoint)라는 것은 두 집합 사이에 공통 원소가 하나도 존재하지 않는다는 의미입니다. 다시 말해, 두 집합의 교집합을 구했을 때 결과가 공집합(∅)이 된다면 그 두 집합은 서로소 관계라고 할 수 있습니다.

판별 방법은 매우 간단합니다. 이 알고리즘에서는 두 개의 집합이 주어지며, 두 집합이 이미 정렬되어 있다고 가정합니다. 이후 두 집합의 원소를 앞에서부터 순차적으로 비교하는데, 일치하는 원소가 하나라도 발견되면 서로소가 아니며, 끝까지 일치하는 원소가 없다면 두 집합은 서로소입니다.

입력 및 출력 예시

입력:
두 개의 집합:
set1: {15, 12, 36, 21, 14}
set2: {7, 89, 56, 32}

출력:
두 집합은 서로소입니다

알고리즘

isDisjoint(set1, set2)

입력: 두 개의 집합

출력: 두 집합이 서로소일 경우 true 반환

Begin
   i1 := 첫 번째 집합의 시작 위치
   i2 := 두 번째 집합의 시작 위치
   while i1이 set1 범위 내에 있고 i2가 set2 범위 내에 있는 동안 반복
      if set1[i1] < set2[i2], then
         i1 := i1 + 1
      else if set2[i2] < set1[i1], then
         i2 := i2 + 1
      else
         return false
   done
   return true
End

동작 원리

정렬된 두 집합을 각각 가리키는 포인터(반복자)를 사용합니다. 한쪽 집합의 현재 원소가 더 작으면 해당 포인터를 한 칸 앞으로 이동시킵니다. 이 과정을 반복하다가 두 원소가 같아지는 순간이 오면 공통 원소가 존재한다는 뜻이므로 즉시 false를 반환합니다. 어느 한쪽 집합의 끝에 도달할 때까지 일치하는 원소가 없었다면 true를 반환하여 서로소임을 알립니다.

이 방식의 시간 복잡도는 두 집합의 크기를 각각 n, m이라 할 때 O(n + m)으로, 모든 원소 쌍을 비교하는 O(n × m) 방식보다 훨씬 효율적입니다.

C++ 구현 예제

#include<iostream>
#include<set>
using namespace std;

bool isDisjoint(set<int> set1, set<int> set2) {
   set<int>::iterator i1, i2;
   i1 = set1.begin(); i2 = set2.begin();       // 반복자를 각 집합의 첫 번째 원소로 초기화
   while(i1 != set1.end() && i2 != set2.end()) {  // 두 집합 모두 확인할 원소가 남아 있는 동안
      if(*i1 < *i2)
         i1++;                               // 첫 번째 집합의 원소가 더 작은 경우
      else if(*i2 < *i1)
         i2++;                               // 두 번째 집합의 원소가 더 작은 경우
      else
         return false;                         // 원소가 일치하면 서로소가 아님
   }
   return true;
}

int main() {
   set<int> set1, set2;
   int n1, n2;
   cout << "Enter number of elements in set 1: "; cin >>n1;

   while(n1 != set1.size()) {   // 중복된 원소는 자동으로 제거됨
      int item;
      cout << "Enter element: "; cin >> item;
      set1.insert(item);
   }

   cout << "Enter number of elements in set 2: "; cin >>n2;
   while(n2 != set2.size()) {
      int item;
      cout << "Enter element: "; cin >> item;
      set2.insert(item);
   }

   if(isDisjoint(set1, set2))
      cout << "Both sets are disjoint";
   else
      cout << "Sets are not disjoint";
}

참고로 C++의 std::set 컨테이너는 내부적으로 항상 정렬된 상태를 유지하므로, 위 알고리즘의 '정렬되어 있다'는 전제 조건을 자연스럽게 만족합니다. 또한 입력 과정에서 중복된 값이 삽입되더라도 set이 자동으로 중복을 제거해 줍니다.

실행 결과

Enter number of elements in set 1: 5
Enter element: 15
Enter element: 12
Enter element: 36
Enter element: 21
Enter element: 14
Enter number of elements in set 2: 4
Enter element: 7
Enter element: 89
Enter element: 56
Enter element: 32
Both sets are disjoint