서로소집합 알고리즘(1)

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 서로소 집합이란

공통원소가 없는 두 집합을 의미한다. 서로소 집합은 서로소 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조로, 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 Union, 특정 원소가 속한 집합은 어느 집합인지 알려주는 Find 연산을 수행할 수 있다. 

 

 

 

▶ 트리자료구조를 이용한 서로소 집합 계산 알고리즘

step 1. 서로 연결된 두 노드 A,B를 확인한다. 두 노드의 루트 노드 A'과 B'을 찾는다. 

step 2. 일반적으로 두 루트 노드 중 더 번호가 작은 원소의 부모노드가 더 큰 원소의 부모 노드가 되도록 설정한다. 즉 번호가 작은 노드가 부모노드가 되고 번호가 큰 노드가 자식노드가 되도록 설정한다. 

step 3. 모든 union연산을 수행할 때 까지 1과 2과정을 반복한다. 

 

 

▷ 예시

{1, 2, 3, 4}라는 집합이 있을 때 다음 2개의 union 연산이 주어진다고 해보자. 

union 2,4 -> 2와 4는 같은 집합임

union 1,2 -> 1과 2는 같은 집합임

union 1,4 -> 1과 4는 같은 집합임

 

step 0. 노드번호대로 부모 노드를 초기화한다. 

step 1+2. union 2,4에 대한 연산을 수행한다. 노드번호 2의 루트노드는 2, 노드번호 4의 루트노드는 4이므로, 노드2의 부모노드를 더 작은 루트노드번호 2로 설정한다.

step 1. union1,2에 대한 연산을 수행한다. 노드1의 루트노드는 1, 노드 2의 루트노드는 2이다.

step 2. 따라서 노드 2의 부모노드를 루트노드 1로 바꾼다.

 

step 1. union 1,4에 대한 연산을 수행한다. 노드 1의 루트노드는 1, 노드 4의 루트노드 역시 1이다. 여기서 주의할 점은 노드 4의 부모노드가 2라고 해서 루트 노드가 2가 아니라는 것이다. 부모노드인 2의 부모노드가 1이므로 결론적으로 노드 4의 루트노드는 1이 되어야한다. 해당 부분은 재귀함수로 구현할 수 있을 것이다.

step 2. 두 노드의 루트 노드가 같으므로 부모노드의 변경은 없다

 

step 3. 모든 연산이 끝이 났으므로 종료한다. 우리는 1,2,4가 서로 같은 집합에 속해있고 3은 다른 집합에 속해있다는 것을 알 수 있다. 

 

 

▷ 구현

먼저 원소의 루트 노드를 찾아주는 함수와 union연산을 수행하는 함수를 선언한다. 

데이터를 입력받고 각 원소들의 루트 노드와 부모노드 정보를 출력한다. 

 

 

예시에서 본 결과와 동일한 결과가 도출되는 것을 볼 수 있다. 

 

이러한 구현 방식의 경우 루트 노드를 확인하는 과정에서 모든 노드를 다 확인해봐야하는 경우가 있으면 시간 복잡도가 O(V)이므로 비효율적인 코드가 될 수 있다. 

이를 최적화하기 위해 경로 압축기법을 사용해 효율성을 높일 수 있다. 해당 구현 방식은 다음 포스팅에서 알아보고자 한다.