그래프 이론

앞서 배운 DFS/BFS와 최단 경로 문제에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 만약 알고리즘 문제를 접했을 때 서로 다른 개체가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 의심해보도록 하자. 여기서는 크루스칼 알고리즘과 위상 정렬 알고리즘을 알아보도록 한다.

서로소 집합

그 전에 먼저 서로소 집합 알고리즘을 배워야 한다. 서로소 집합은 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)

 

또한 이를 이용하여 사이클을 판별할 수도 있다.

 

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)

신장 트리

신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 

크루스칼 알고리즘

크루스칼 알고리즘은 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘이다. 핵심 원리는 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다는 것이다. 다만, 사이클을 발생시키는 간선은 제외한다.

 

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)

edges = []
result = 0

for i in range(1, v+1):
    parent[i] = i
    
for i 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

위상 정렬

위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 여기서는 진입 차수라는 개념이 나오는데, 진입 차수란 특정한 노드로 들어오는 간선의 개수를 의미한다. 동작 방식은 아래와 같다.

 

1. 진입 차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
   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) # 정점 A에서 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()