[이코테] chap10. 그래프 이론

서로소 집합

서로소 집합(Disjoint Sets)은 공통 원소가 없는 두 집합을 의미한다.
이때 집합 간의 관계를 파악하기 위해 서로소 집합 알고리즘을 사용할 수 있는데, 서로소 집합 알고리즘은 union-find 연산으로 구성되며, 모든 노드는 자신이 속한 집합을 찾을 때 루트 노드를 재귀적으로 찾는다.
(즉, 루트 노드가 같으면 같은 집합으로 본다.)
서로소 집합 알고리즘은 최소 신장 트리를 찾는 크루스칼 알고리즘에서 사용되기도 하므로 중요하다.

• union 연산을 확인하며, 서로 다른 두 원소에 대해 합집합(같은 그룹으로 합치기)을 진행할 땐, 각각의 루트노드를 찾아 큰 루트노드가 더 작은 루트를 가리키도록 구현한다.
• 시간 복잡도: O(V + M(1 + log2-m/vV))

서로소 집합 구현 코드

# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(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=' ')

서로소 집합의 사이클 판별

• 서로소 집합을 이용하면 사이클 판별도 가능하다.
• 무방향 그래프 내에선 사이클을 판별할 수 있다. 참고로 방향 그래프의 사이클은 DFS로 판별 가능하다.

1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.(find 함수 호출)
   1) 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행한다.
   2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것이다.
2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복한다.

=> 사실 앞선 코드에서 input인 간선들을 확인하면서, 루트 노드가 같은 것이 있는지 확인하는 것.

# 특정 원소가 속한 집합을 찾기
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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
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
    # 사이클이 발생하지 않았다면 합집합(Union) 연산 수행
    else:
        union_parent(parent, a, b)

if cycle:
    print("사이클이 발생했습니다.")
else:
    print("사이클이 발생하지 않았습니다.")

신장 트리(Spanning Tree)

하나의 그래프에서 모든 노드를 다 포함하고 사이클이 없는 트리를 의미한다.
일반적인 그래프에서 신장 트리를 추출하는 예시는 다음 그림과 같다.
이러한 신장 트리 구성 문제는 현실 세계에서 '모든 섬을 도로를 이용해 연결하는 문제'등에서 사용할 수 있다.

• 대표적인 신장트리 알고리즘으로,
  무방향 그래프 -> 크루스칼 알고리즘(최소 비용의 신장 트리)
  방향 그래프 -> 위상 정렬 알고리즘

크루스칼(Kruskal) 알고리즘

신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘

• 대표적인 최소 신장 트리 알고리즘(MST)
• 간선의 비용이 작은 순서대로 정렬한 뒤 차례대로 최소 신장 트리를 만들어 가는 그리디 알고리즘의 일종이다.
• 시간 복잡도 $O(ElogE)$ (E - 간선 수)

즉, 비용이 작은 간선부터 트리를 만들면 된다. 

알고리즘

1. 간선 테이블은 비용을 기준으로 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   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

# 노드의 개수와 간선(Union 연산)의 개수 입력 받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화하기

# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력 받기
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

print(result)

 

위상 정렬 알고리즘

방향 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법이다.
예) '선수 과목을 고려한 학습 순서 설정 문제'등에서 사용될 수 있다.

• 큐 자료구조를 이용한 위상 정렬의 시간 복잡도는 O(V + E) 이다.
• 진입 차수(indegree) : 특정한 노드로 '들어오는' 간선의 개수

 

알고리즘

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   (이러면 진입차수가 0이된 노드가 생성된다.)
   2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

코드

from collections import deque  

# 노드의 개수와 간선의 개수를 입력 받기  
v, e = map(int, input().split())  
# 모든 노드에 대한 진입차수는 0으로 초기화  
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) # 정점 A에서 B로 이동 가능  
    # 진입 차수를 1 증가  
    indegree[b] += 1  

# 위상 정렬 함수  
def topology_sort():  
    result = [] # 알고리즘 수행 결과를 담을 리스트  
    q = deque() # 큐 기능을 위한 deque 라이브러리 사용  

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입  
    for i in range(1, v + 1):  
        if indegree[i] == 0:  
            q.append(i)  

    # 큐가 빌 때까지 반복  
    while q:  
        # 큐에서 원소 꺼내기  
        now = q.popleft()  
        result.append(now)  
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기  
        for i in graph[now]:  
            indegree[i] -= 1  
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입  
            if indegree[i] == 0:  
                q.append(i)  

    # 위상 정렬을 수행한 결과 출력  
    for i in result:  
        print(i, end=' ')  

topology_sort()

서로소 집합 알고리즘과 최소 신장 알고리즘은 종종 코테에 출제되는 유형이며,
위상 정렬은 난이도가 높은 후반부 문제에 가끔 출제된다.