💻코딩테스트
[이코테_코딩테스트] 그래프 - 서로소 집합 자료구조
서로소 집합 (Disjoint Sets)
- 공통 원소가 없는 두 집합을 의미한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F014f1bec-e846-439e-9602-b003b95fa9e5%2FUntitled.png?table=block&id=2d319722-44d3-4e05-a39e-94638f98c255&cache=v2)
서로소 집합 자료구조
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 서로소 집합 자료구조는 두 종류의 연산을 지원한다.
- 합집합 (Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- 찾기 (Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
- 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 한다.
여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정
- 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
- A와 B의 루트 노드 를 각각 찾는다.
- 를 의 부모 노드로 설정한다.
- 모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복한다.
서로소 집합 자료구조 동작 과정
- 처리할 연산들 :
[초기 단계] 노드의 개수 크기의 부모 테이블을 초기화한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fa12dad78-c4d5-420f-9dd2-2b07d71a768d%2FUntitled.png?table=block&id=3f010bfa-ae2b-4d53-86b8-f15699be600d&cache=v2)
[Step 1] 노드 1과 노드 4의 루트 노드를 찾는다.
- 현재 루트 노드는 각각 1과 4이므로 더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fb769ac08-0576-46c7-98f2-6b80413a1338%2FUntitled.png?table=block&id=0b53d1ba-83fe-45db-b49d-79c68c728439&cache=v2)
[Step 2] 노드 2과 노드 3의 루트 노드를 찾는다.
- 현재 루트 노드는 각각 2와 3이므로 더 큰 번호에 해당하는 루트 노드 3의 부모를 2로 설정한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F463088da-01d8-431b-9840-fd76f3e7356b%2FUntitled.png?table=block&id=330d9ed7-8f86-4cb9-9617-0f616becbb76&cache=v2)
[Step 3] 노드 2과 노드 4의 루트 노드를 찾는다.
- 현재 루트 노드는 각각 2와 1이므로 더 큰 번호에 해당하는 루트 노드 2의 부모를 1로 설정한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F07a75718-4824-4eec-a19f-0ca5fa87d896%2FUntitled.png?table=block&id=2b7d399d-09ab-4dae-8a79-36ef1a7a92c5&cache=v2)
- 3번 노드와 4번 노드는 같은 집합으로 연결되어 있다고 확인할 수 있다.
- 하지만, 3번 노드의 부모 노드는 2, 4번 노드의 부모 노드는 1이다.
- 실제로 두 원소가 같은 집합에 포함되어 있는지 확인하기 위해서는 루트 노드를 찾을 수 있도록 해야한다.
- 3번 노드의 부모를 확인하면 2번 노드가 나오고, 2번 노드의 부모 노드를 확인하면 1번 노드가 나온다.
- 따라서, 3번 노드의 루트 노드인 1과 4번 노드의 루트 노드인 1이 같기 때문에
3번 노드와 4번 노드는 서로 같은 집합에 속해있다고 판단할 수 있다.
[Step 4] 노드 5과 노드 6의 루트 노드를 찾는다.
- 현재 루트 노드는 각각 5와 6이므로 더 큰 번호에 해당하는 루트 노드 6의 부모를 5로 설정한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F87731fe3-b82f-4152-877a-2e5fc1a38618%2FUntitled.png?table=block&id=6f480d2f-5843-4c80-948e-c13087865617&cache=v2)
서로소 집합 자료구조에서 연결성을 통해 손쉽게 집합의 형태를 확인할 수 있다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F8d7051bc-7f27-4a0c-9d99-e6ae59c464ce%2FUntitled.png?table=block&id=1d33b797-ac17-43cc-80d7-e8ed06aabc99&cache=v2)
- 기본적인 형태의 서로소 집합 자료구조에서는 루트 노드에 즉시 접근할 수 없다.
- 루트 노드를 찾기 위해 부모 테이블을 계속해서 확인하며 거슬러 올라가야 한다.
- 다음 예시에서 노드 3의 루트를 찾기 위해서는 노드 2를 거쳐 노드 1에 접근해야 한다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F67a945b9-f64e-4b2b-bbb5-3551709a548a%2FUntitled.png?table=block&id=2d4f0b98-dd72-43dc-9c09-3e7257af825d&cache=v2)
서로소 집합 자료구조 - 기본적인 구현 방법 (Python)
# 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드 찾을 때까지 재귀 호출 if parent[x]!= x: # 부모 노드 != 자신 => 루트 노드가 아님 return find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합 찾기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b # 노드의 개수와 간선(Union 연산)의 개수 입력 받기 v, e = map(int, input().split()) # 부모 테이블 초기화 parent = [0] * (v + 1) # 부모 테이블상에서 부모를 자기 자신으로 초기화 for i in range(1, v + 1): parent[i] = i # Union 연산 수행 for i in range(e): a, b = map(int, input().split()) union_parent(parent, a, b) # 각 원소가 속한 집합 출력 print("각 원소가 속한 집합 : ", end='') for i in range(1, v + 1): print(find_parent(parent, i), end=' ') print() # 부모 테이블 내용 출력 print("부모 테이블 : ", end='') for i in range(1, v + 1): print(parent[i], end=' ')
서로소 집합 자료구조 - 기본적인 구현 방법의 문제점
- 합집합(Union) 연산이 편향되게 이루어지는 경우 찾기(Find) 함수가 비효율적으로 동작한다.
- 찾기(Find) 함수는 매번 현재 노드에서 부모 테이블을 참조하여 부모가 자기 자신이 아니라면,
루트가 아니라는 것이므로 자신의 부모에 대해 다시 한 번 재귀적으로 호출한다.
- 최악의 경우에는 찾기(Find) 함수가 모든 노드를 다 확인하게 되어 시간 복잡도가 이다.
- 다음과 같이 {1, 2, 3, 4, 5}의 총 5개의 원소가 존재하는 상황
- 수행된 연산들 :
- 5번 노드의 루트 노드를 알려면 5 → 4 → 3 → 2 → 1
- 즉, 모든 노드에 대해서 함수를 호출하게 된다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fa0fbb982-c381-49fd-a775-6a8685986cb6%2FUntitled.png?table=block&id=64e69e82-5f7e-4aec-bd50-60e2cb9119fc&cache=v2)
서로소 집합 자료구조 - 경로 압축
- 찾기(Find) 함수를 최적화하기 위한 방법으로 경로 압축(Path Compression)을 이용할 수 있다.
- 찾기(Find) 함수를 재귀적으로 호출한 뒤에 부모 테이블 값을 바로 갱신한다.
# 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드 찾을 때까지 재귀 호출 if parent[x]!= x: # return find_parent(parent, parent[x]) parent[x] = find_parent(parent, parent[x]) return parent[x] # 다른 코드는 기본적인 구현과 동일
- 경로 압축 기법을 적용하면 각 노드에 대하여 찾기(Find) 함수를 호출한 이후에 해당 노드의 루트 노드가 부모 노드가 된다.
- 위와 동일한 예시에 대해 모든 합집합(Union) 함수를 처리한 후 각 원소에 대하여 찾기(Find) 함수를 수행하면 다음과 같이 부모 테이블이 갱신된다.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F3aec036b-06a4-4612-86be-ebe6243ba4b9%2FUntitled.png?table=block&id=7b04af85-2ebc-4673-9565-6f7d3cc6e321&cache=v2)
- 기본적인 방법에 비하여 시간 복잡도가 개선된다.
이 글은 유튜브 “동빈나” 채널의 “(이코테 2021 강의 몰아보기) 8. 기타 그래프 이론” 영상을 보고 작성하였습니다.