파이썬 알고리즘 공부 - (5) 기타 (서로소 집합, 신장트리, 위상정렬)

 

📍서로소 집합

: 공통 원소가 없는 두 집합을 의미함

- 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

- 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

서로소 집합 자료구조는 두 종류의 연산을 지원한다.

 

합집합 연산이 편향되게 이루어질 경우 비효율적으로 동작

최악의 경우 시간복잡도 : O(V) (모든 노드를 다 확인해야 함)

#특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
	if parent[x] != x: #루트 노드를 찾을 때까지 재귀호출
    	return find_parent(parent, parent[x])
    return x
    
# 2. 경로 압축 방법으로 find함수
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

#노드개수, 간선 입력받기
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)
    
# 각 원소가 속한 집합 
for i in range(1, v+1):
	print(find_parent(parent, i), end='')
    
# 부모 테이블 내용 출력
for i in range(1, v+1):
	print(parent[i], end='')

 

 

서로소 집합을 이용하여 무방향 그래프 내에서의 사이클을 판별할 수 있다. 

(*방향그래프 판별은 DFS)

1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인, 다르다면 합집합 연산 수행 / 같다면 사이클이 발생한 것

2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 반복

 

루트 노드가 다 같다면 사이클이 발생한 것

 

for i in range(e):
	a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b):
    	cycle = True
        break
    else:
    	union_parent(parent, a, b)

 

📍신장 트리

: 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미

 

크루스칼 알고리즘

- 대표적인 최소 신장 트리 알고리즘, 그리디 알고리즘

1. 간선 데이터를 비용에 따라 오름차순 정렬

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 ( 사이클 발생 X :최소 신장 트리에 포함, 사이클 발생 : 포함 X)

3. 모든 간선에 대해 2번 반복

- 간선의 개수가 E개일 때 시간복잡도 : O(ElogE)

# find_parent(parent, x), union_parent(parent, a, b) 활용
# 크루스칼 알고리즘

for _ in range(e):
	a, b, cost = map(int, input().split())
    edges.append(cost, a, b)

edges.sort() #비용을 기준으로 오름차순 정렬

for edge in edges:
	cost, a, b = edge
    # 사이클 발생하지 않는다면 합치기, 비용 더하기 
    if find_parent(parent, a) != find_parent(parent, b):
    	union_parent(parent, a, b)
    	result += cost
   
return result

📍위상 정렬

: 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미

- 큐를 이용하는 위상 정렬 알고리즘

1. 진입차수가 0인 모든 노드를 큐에 넣는다. 

1-1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선 그래프를 제거한다.

1-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 

2. 큐가 빌 때까지 반복

 

*진입차수: 특정한 노드로 들어오는 간선의 개수

*진출차수: 특정한 노드에서 나가는 간선의 개수

 

- 여러 가지 답이 존재할 수 있다.

- 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 

- 스택으로 이용할 수도 있다. 

- 시간 복잡도 : O(V+E)

 

from collections import deque

v, e = map(int, input().split())
indegree = [0]*(v+1) 	# 진입차수 초기화
graph = [[] for i in range(v+1)]

for _ in range(e): #  간선 정보 입력받기
	a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1
    
# 위상정렬 함수
def topology_sort():
	result = []
    q = deque()
    for i in range(1, v+1):
    	if indegree[i] == 0:
        	q.append(i)
    # 큐가 빌 때까지 반복
    while q:
    	now = q.popleft()
        result.append(now)
        for i in graph[now]:
        	indegree[i] -= 1
            if indegree[i] == 0:
            	q.append(i)
    for i in result:
    	print(i, end='')
        
topology_sort()