📈그래프 알고리즘

이전 포스트에서 그래프 탐색을 기반으로하고 그래프 자료구조 형태에서 사용할 수 있는 다양한 알고리즘에 대한 소개를 한다.

📊분리 집합 (Union-Find)

분리집합 또는 서로소 집합 이라고 불리는 Union-Find 알고리즘은 공통 원소가 없는 두 집합을 의미한다. 이 자료구조는 서로소 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.

이 자료구조에는 2가지의 연산이 존재하는데 말 그대로 Union 연산과 Find 연산이다.
Union은 2개의 원소가 포함된 집합 2개를 하나로 합쳐주는 집합이며, Find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.

아래는 Union-FInd 자료구조의 기본적인 형태이다.

n = int(input())
parent = [i for i in range(n+1)]

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    a = find(a)
    b = find(b)

    if a > b:
        parent[a] = b

    else:
        parent[b] = a


for i in range(int(input())):
    a, b = map(int, input().split())
    union(a, b)
    print(parent)

예를 들어 다음 테스트 케이스를 위 코드에 넣었을 떄 출력값은 다음과 같다

# input
5
4
1 2
2 3
3 4
4 5

# output
[0, 1, 1, 3, 4, 5]
[0, 1, 1, 1, 4, 5]
[0, 1, 1, 1, 1, 5]
[0, 1, 1, 1, 1, 1]

위 코드의 경우 5개의 입력을 받는다. 5개는 각각의 독립적인 집합에 속해있는다.
4개의 union 연산을 통해 1, 2를 합치고, 2, 3을 합치고,,, 이 과정을 반복한다.

그렇게 했을 때 parent 리스트가 변하는 것을 보면, 더 번호가 앞서는 것으로 해당 노드의 parent 값이 변하는 것을 볼 수 있다.

트리로 나타낸다면 다음과 같이 표현 할 수 있을 것이다.

초기 상태가 다음과 같다면 UNION 연산이 진행된 경우는 아래 그림처럼 된 것을 볼 수 있다.

코드자체가 어렵지 않으므로 크게 설명할 것이 없으니 대략적인 매커니즘만 정리한다.

우선 find 연산의 경우 재귀 호출을 통해 현재 노드값과 부모 값이 같아질 때까지 탐색해 나간다.
사실 저 코드에는 경로 압축 기법이 녹아들어 있는데 위 과정을 직관적으로 구현하면 아래 코드처럼 작성할 수 있을 것이다

def find(a):
	if parent[a] != a:
    	return parent(parent[x])
    return x

위 알고리즘을 그대로 쓰게 된다면 순서대로 부모 노드를 거슬러 올라가야 하므로 최대 $O(N)$의 시간이 들어갈 수 있다. 그렇게 되면 노드의 개수가 $V$이고, 연산의 개수가 $M$개일 때 $O(VM)$이 되어버린다.

경로 압축이 적용된 원래 코드를 보면 각 노드에 대하여 find 함수를 호출한 이후에 해당 노드의 루트 노드가 바로 부모 노드가 되므로 시간복잡도에서 효율적으로 동작한다.

union 연산은 두개의 부모를 찾은 다음 순서상 빠른 노드의 부모의 번호에 다른 노드를 합치는 방식이다.

최종적으로 시간복잡도는 $V + M \log_{2 - M/V}V$ 이다.

분리집합에서 사이클(Cycle) 판정

MST의 가장 기본적인 알고리즘 중 하나인 크루스칼 알고리즘에 응용하기 위해 필요한 지식이다.
우선 사이클이라는 것이 무엇인지부터 정의한다.

위 트리에서 주황색으로 표시된 부분이 사이클이다.
즉 간선이 시작한 노드와 끝난 노드가 같으면 사이클이 생겼다라고 표현한다.

사이클 판정 과정은 다음 수식을 따른다

if find(a) == find(b):
	isCycle = True
    break

else:
	union(a, b)

예제

[BOJ-1717] 집합의 경로

문제
기본적인 서로소 집합을 찾는 문제. 합집합 연산 때 Union을 하고 부모가 같은지 확인하여 YES 또는 NO를 출력한다.

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a


n, m = map(int, input().split())
parent = [i for i in range(n+1)]
for i in range(m):
    q, a, b = map(int, input().split())
    if q:
        print("YES" if find(a) == find(b) else "NO")
    else:
        union(a, b)

🎄신장 트리

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

크루스칼 알고리즘

최소 신장 트리를 찾는 알고리즘이다. 최소 신장트리는 MST라고도 불리며, 다음과 같은 상황에서 사용된다.
$N$개의 도시가 존재할 때 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치할 때 최소 비용으로 도로를 연결하는 경우.

크루스칼 알고리즘은 그리디 알고리즘으로 분류가 된다. 구체적인 동작 과정은 아래와 같다.

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

2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인한다

   • 사이클이 발생하지 않는 경우 MST에 포함시킨다
   • 사이클이 발생하는 경우 MST에 포함시키지 않는다.

3. 모든 간선에 대해 2번 과정을 반복한다.

크루스칼 알고리즘은 트리 자료구조이므로 최종적으로 신장 트리에 포함되는 간선의 개수가 노드의 개수 - 1을 만족한다. 따라서 크루스칼 알고리즘의 핵심은 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다는 것이다. 이렇게 하면 항상 최적해를 보장할 수 있다.

기본적으로 사이클 판정은 Union-Find를 사용하므로 해당 연산을 하는 함수는 생략한다.

for edge in edges:
	cost, a, b = edge
	if find(a) != find(b):
    	union(a, b)
        result += cost
print(result)

크루스칼 알고리즘의 경우 간선의 개수가 $E$일때 $O(E \log E)$의 시간복잡도를 가진다. 크루스칼 알고리즘에서 가장 오래 걸리는 작업은 간선을 정렬하는 과졍이며 내부에서 사용하는 Union-Find의 시간복잡도는 작으므로 무시한다.

예제

[BOJ-18769] 그리드 네트워크

문제
그래프의 간선 정보가 주어지면 노드를 잇는 최소 비용을 구하는 문제. 그래프를 구현하는데 꽤 어려웠음.
나머지는 MST의 기본을 이용하면 금방 구할 수 있다.

def find(x, parent):
    if x != parent[x]:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(x, y, parent):
    x, y = find(x, parent), find(y, parent)
    if x > y:
        parent[x] = y
    else:
        parent[y] = x

def solve():
    r, c = map(int, input().split())
    parent = [i for i in range(r*c+1)]
    graph = []

    for i in range(r):
        weight = list(map(int, input().split()))
        for j in range(c-1):
            node = i * c + j
            graph.append((weight[j], node, node+1))
    
    for i in range(r-1):
        weight = list(map(int, input().split()))
        for j in range(c):
            node = i * c + j
            graph.append((weight[j], node, node + c))
    
    graph.sort(key=lambda x: x[0])
    result = 0
    for e in graph:
        weight, a, b = e
        if find(a, parent) != find(b, parent):
            union(a, b, parent)
            result += weight
    
    return result
       

if __name__ == "__main__":
    for i in range(int(input())):
        print(solve())

[BOJ-21924] 그리드 네트워크

문제
위 문제보다 조금 더 기본형에 가까운 문제. MST를 이용하면 됨 마지막에 모든 구간이 연결되었는지 확인하는 부분을 주목할것.

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x, y = find(x), find(y)
    if x > y:
        parent[x] = y

    else:
        parent[y] = x

n, m = map(int, input().split())
graph = [tuple(map(int, input().split())) for _ in range(m)]
parent = [i for i in range(n+1)]
graph.sort(key=lambda x: x[2])
mmax = sum(list(zip(*graph))[2])

res = 0
for a, b, cost in graph:
    if find(a) != find(b):
        union(a, b)
        res += cost

tmp = 0
for i in range(1, n+1):
    if parent[i] == i:
        tmp += 1

print(mmax - res if tmp == 1 else -1)

🔮위상 정렬

위상 정렬은 정렬 알고리즘의 일종이다. 순서가 정해져 있는 일련의 작업을 차례대로 수행할 떄 사용할 수 있는 알고리즘이다. 이론적인 설명으로는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다.

현실세계에서 사용하는 예시로는 "선수과목을 고려한 학습 순서 설정"을 들 수 있다. 그래프 상에 선후관계가 있다면 위상정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.

진입차수(indegree)는 특정한 노드로 들어오는 간선의 개수를 의미한다. 예를들어 A → B → C 로 가는 그래프가 있을떄 C는 2개의 진입차수를 가진다.

위상정렬 알고리즘은 아래와 같다.

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

위상정렬 기본형 코드는 아래와 같다. 위 매커니즘을 그대로 따른 코드이다.

from collections import deque

v, e = map(int, input().split())
indegree = [0] * (v+1)
graph = [[] for _ 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)
    return result

print(topology_sort())

예제

[BOJ-14567] 선수과목

문제

기본적인 위상정렬을 하되, 정렬되는 노드가 아니라 indegree의 값을 물어보는 문제. 진입차수가 업데이트 될때마다 바뀌는 값들을 result에 저장하는 방식으로 풀이함.

import sys
from collections import deque
input = sys.stdin.readline

v, e = map(int, input().split())
indegree = [0] * (v+1)
graph = [[] for _ 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 = [0] * (v+1)
    q = deque()

    for i in range(1, v+1):
        if indegree[i] == 0:
            result[i] = 1
            q.append(i)
 
    while q:
        now = q.popleft()

        for i in graph[now]:
            indegree[i] -= 1
            result[i] = result[now] + 1
            if indegree[i] == 0:
                q.append(i)
    return result

print(*topology_sort()[1:])