chapter 10. 그래프 이론(Union-Find, 크루스칼, 최소 신장 트리 알고리즘)

 

 알고리즘 문제를 접했을 때 '서로 다른 개체가 연결되어 있다' = '여러 개의 도시가 연결되어 있다'와 같은 내용이 나오면 그래프 알고리즘을 의심해보자

 

1. union-find(합집합 찾기, 서로소 집합)

차후 크루스칼 알고리즘과 위상 정렬에서 사이클이 발생했는지 판별할 때 사용한다

union-find 연산을 통해 최종 부모노드를 찾아가는 알고리즘이다

union(A, B)를 한다면 둘 중 부모노드의 값이 더 작은 노드로 합쳐진다

 

 

 

 

① 그래프 생성

 

 부모 노드 배열을 만들고 자기자신을 가리키는 것으로 초기화한다

union(4, 5) -> union(3, 4) -> union(2, 3) -> union(1, 2) 순으로 진행하기로 한다

 

 

 

② union(4, 5)

 union(4, 5)가 진행되면 4와 5번 노드 중 부모노드 값이 작은 노드로 합쳐지게 된다

4가 5보다 작으므로 4로 합쳐진다

 

 

 

③ union(3, 4)

 위의 연산과 같이 부모노드가 작은 3노드로 4가 합쳐지게 된다

노드가 3 <- 4 <- 5 를 가리키는 것으로 입력된다

 

 

 

union(2, 3), union(1, 2) 생략

 

 

 

④ 최종 union 테이블

 

 연산을 반복하면 다음과 같이 테이블이 완성된다.

하지만 이렇게 되면 find 함수가 비효율적으로 동작한다. 

5의 부모를 찾고 싶으면 노드 4로 각 노드 4의 부모 3을 찾고 노드 3의 부모 2를 찾고 .... 를 반복해야 돼서 비효율적이다

이제 이를 해소해 줄 find연산을 해준다

 

 

 

⑤ find(1), find(2)

 노드 1의 부모는 1이므로 동일하다 다음으로 넘어간다

 노드 2의 부모는 1이고, 노드 1의 부모는 1이므로 동일하다 테이블 상 변화는 없다

 

 

 

⑦ find(3)

 노드 3의 부모는 2이다.

노드값과 부모의 값이 일치하지 않으므로(=부모의 값이 더 있는 것) 노드 2의 부모를 찾아가보자.

노드 2의 부모는 1이고 노드 1의 부모는 1이다

이제 노드값과 부모의 값이 일치하게 됐다. (노드 1 = 부모 1)

이 부모의 값 1을 노드 3의 부모에 입력해준다

 

 

 

 

⑧ find(4), find(5)

 같은 방식으로 find(4), find(5)를 실행하면 다음과 같은 테이블이 만들어진다

 

 

 

노드 2, 3, 4, 5의 최종적인 부모는 1인 것으로 테이블이 완성된다

 

 

 

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

 

 

 

 

2. 크루스칼 알고리즘

 가장 작은 거리값들을 찾아 최소 비용으로 전체 도시를 연결될 수 있게 만드는 알고리즘이다

단, 도시 간의 사이클은 형성되면 안 된다 = Union-Find 사용

시간복잡도는 O(ElogE)이다

 

 

 

다익스트라	플로이드-워셜	크루스칼
특정 노드에서 다른 노드로 가는 최소거리	모든 노드에서 모든 노드로 가는 최소거리	모든 노드가 연결되지만 사이클은 발생하지 않는 최소거리 최소 신장 트리 = 최소 스패닝 트리(MST, Minimum Spanning Tree) 라고 한다

 

 

 

 

 

step 1. 간선 중 비용이 가장 적은 간선 (3, 4)를 선택한다

step 2. 남은 간선 중 비용이 가장 적은 간선 (4, 7)를 선택한다

step 3. 남은 간선 중 비용이 가장 적은 간선 (4, 6)를 선택한다

step 4. 남은 간선 중 비용이 가장 적은 간선 (6, 7)을 선택하면 (4, 7)과 (4, 6)이 이미 선택돼있으니 사이클이 발생한다

          (6, 7)은 선택하지 않고 넘어간다.

 

 

 

 

 최종적인 최소 스패닝 트리는 위와 같다

 

 

 

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

 

 

 

 

3. 위상 정렬(=Topology Sort)

순서가 정해져있는 작업을 순서대로 일렬로 나열하기 위한 알고리즘이다
답이 여러개 나올 수도 있다

시간복잡도는 O(V+E)이다

 

 

 

 

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

2. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

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

4. 2, 3번을 반복한다.

 

 

 

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

 

 

 

① 팀 결성

import sys
input=sys.stdin.readline
 
# 특정 원소가 속한 집합을 찾기
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(v + 1):
    parent[i] = i
 
for _ in range(e):
    k, a, b = map(int, input().split())
    if k==1: #find 연산
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')
 
    elif k==0: #union 연산
        union_parent(parent, a, b)
 

 

 

② 도시 분할 계획

 

 

 

③ 커리큘럼

 

 

 

 

 

 

출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html