2021.3.1 알고리즘(분리 집합)

1. 분리집합

 

서로소 집합이라고도 하는 분리집합(Disjoint Sets)은 공통 원소가 없는 두 집합을 말한다.

분리집합 자료구조에서는 union 연산과 find 연산을 사용한다.

시간복잡도는 O(V+M(1+logV))정도 이다.

 

코드는 다음과 같다.

 

def find_parent(x): #루트 노드 탐색
    if p[x] != x:
        p[x] = find_parent(p[x])
    return p[x]

def union(x, y): #합집합 
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        p[y] = x
    else:
        p[x] = y

 

v, e = map(int, input().split()) #노드 개수와 간선 개수 입력받기

p = [0] * (v+1) #부모 테이블 초기화

for i in range(1, v+1):

    p[i] = i

 

for i in range(e): #간선 정보 입력받기. 문제마다 이 부분 달라질 수 있음

    a, b = map(int, input().split())

    union(a, b)

 

print(p[1:]) #부모 테이블 출력

 

 

2.  크루스칼 알고리즘

 

크루스칼 알고리즘(Kruskal Algorithm)이란 최소 신장 트리 알고리즘이라고도 한다.

하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미하며 가장 적은 비용으로 모든 노드를 연결할 수 있다.

크루스칼 알고리즘은 시간복잡도가 O(ElogE)이다.

 

코드는 다음과 같다.

 

def find_parent(x): #루트 노드 탐색
    if p[x] != x:
        p[x] = find_parent(p[x])
    return p[x]

def union(x, y): #합집합 
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        p[y] = x
    else:
        p[x] = y

 

v, e = map(int, input().split()) #노드 개수와 간선 개수 입력받기

p = [0] * (v+1) #부모 테이블 초기화

for i in range(1, v+1):

    p[i] = i

 

array = [] #간선을 담을 리스트

result = 0 #최종 비용을 담을 변수

 

for i in range(e): #간선 정보 입력받기. 문제마다 이 부분 달라질 수 있음

    a, b, cost = map(int, input().split())

    array.append((cost, a, b)) #비용순으로 정렬하기 위해 튜플 첫번째 원소를 cost로 한다.

 

array.sort()

 

for k in array:

    cost, a, b = k

    if find_parent(a) != find_parent(b): #사이클이 발생하지 않을 경우에만 집합에 포함하고 비용 더하기

        union(a, b)

        result += cost

 

print(result)