📖 서로소 집합 자료구조

공통 원소가 없는 두 집합

• 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
• 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산

동작 과정

그림과 같은 식으로 부모 노드를 설정하며 트리를 만든다

예제 코드

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = 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)

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=' ')

재귀함수를 활용한 find_parent와 union_parent 메서드를 이용해서 구현한다

💡 서로소 집합을 활용한 사이클 판별

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

• 방향 그래프에서의 사이클 여부는 DFS를 이용하여 핀별

동작 과정

예제 코드

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = 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

cycle = False

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)

if cycle:
    print('사이클이 발생')
else:
    print('사이클이 발생하지 않음')

이전 서로소 집합 코드를 수정하여 구현한다

동작 과정과 같이 a와 b를 연결하기 전에 부모가 같다면 사이클이 발생한 것이기 때문에 cycle을 발생시킨다

📖 신장 트리

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

최소 신장 트리

최소 비용으로 신장 트리를 만드는 경우

💡 크루스칼 알고리즘

• 최소 신장 트리 알고리즘
• 그리디 알고리즘으로 분류

동작과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인

• 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
• 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음

3. 모든 간선에 대하여 2번 과정 반복

예제 코드

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = 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())
edges = []
result = 0

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

parent = [0] * (v + 1)
for i in range(1, v + 1):
    parent[i] = i

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

print(result)

간선과 비용을 저장하는 edges 리스트를 만든다

그리고 edges를 비용을 기준으로 오름차순으로 정렬한다

비용이 작은 간선부터 a, b를 union 해주는데 만약 부모가 같다면 사이클이 발생한 상황이니까 부모가 같지 않을 때만 간선을 이어준다.

성능

간선의 개수가 E개일 때, O(ElogE)의 시간 복잡도를 가진다

📖 위상 정렬

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

• 방향성이 있는 그래프이고, 사이클이 없어야한다
• 진입차수: 특정한 노드로 들어오는 간선의 개수
• 진출차수: 특정한 노드에서 나가는 간선의 개수
  

동작 과정

1. 진입차수가 0인 모든 노드를 큐에 넣는다
2. 큐가 빌 때까지 다음의 과정을 반복한다

• 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
• 새롭게 진입차수가 0이 된 노드를 큐에 넣는다

예제 코드

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()

성능

차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 제거하는 과정이니 시간 복잡도는 O(V + E)이다