개념
서로소 집합 알고리즘은 말 그대로 어떠한 숫자들의 서로소인지 아닌지의 관계를 나타내는 알고리즘이라고 생각하시면 될 것 같습니다. 먼저 1, 2라는 집합과 3, 4라는 집합이 있다고 가정합시다. 이 두 집합은 교집합이 없기 때문에 서로소 관계라고 할 수 있습니다. 우리가 구현할 서로소 집합 알고리즘의 경우 부모를 확인하는 함수, 합치기 연산을 수행하는 함수로 크게 두 부분으로 나눌 수 있습니다. 단 부모를 확인하는 함수에서 경로 압축 기법을 사용하게 되면 보다 빠른 시간 복잡도로 문제를 해결할 수 있기 때문에 외워주는 것이 좋을 것 같습니다.
소스코드
본 소스코드는 나동빈님의 이것이 취업을 위한 코딩테스트이다. 를 참조하였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
def find_parnet(parent, x):
# 루트 노드가 아니면, 루트 노드를 찾을때까지 재귀적으로 찾기
if parent[x] != x:
parent[x] = find_parnet(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_Parent(parent, a, b):
a = find_parnet(parent, a)
b = find_parnet(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0] * (v + 1)
for i in range(1, v + 1):
parent[i] = i
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_parnet(parent, i), end=" ")
print()
print("부모 테이틀: ",end="")
for i in range(1, v + 1):
print(parent[i], end=" ")
|
cs |
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| 크루스컬 알고리즘 (Python) (0) | 2020.12.31 |
|---|---|
| 사이클 판별 알고리즘 (Python (0) | 2020.12.31 |
| 다익스트라 알고리즘 (Python) (0) | 2020.12.22 |
| 편집거리 알고리즘 (Python) (0) | 2020.12.22 |
| 에라토스테네스의 체를 이용한 소수 판별 (Python) (0) | 2020.12.21 |