[1197번] 최소 신장 트리(MST, 크루스칼, 프림, 유니온파인드)

1197번: 최소 스패닝 트리

 

 

최소 신장 트리

• 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것
• 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1

크루스칼 알고리즘

• 간선 위주의 알고리즘
• 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입 하면서 트리를 구성하기 때문에 사이클이 이루어지는 항상 확인 해야한다.
• 크루스칼은 간선을 기준으로 정렬하는 과정이 오래 걸린다.
• 그래프 내에 적은 숫자의 간선만을 가지는 ‘희소 그래프(Sparse Graph)’의 경우 Kruskal 알고리즘이 적합, Kruskal 알고리즘의 시간 복잡도는 O(elog₂e)
• 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

1. 최소 비용의 간선으로 구성됨
2. 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.

 동작원리

1. 모든 간선들의 가중치를 오름차 순으로 정렬
2. 가중치가 가장 작은 간선을 선택
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 이 과정을 반복

프림 알고리즘

• 시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하며 신장 트리를 확장 시키는 알고리즘
• 정점 선택을 기반으로 하는 알고리즘
• 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리르 구성 하므로 그 과정에서 사이클을 이루지 않음
• 프림의 경우 최소 거리의 정점을 찾는 부분에서 자료구조의 성능에 영향을 받는다.
• 그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합, Prim의 알고리즘의 시간 복잡도는 O(n^2)

동작 원리

1. 임의의 간선을 선택
2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택
3. 모든 정점이 선택될 때까지 반복

 

원리

1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기 : 싸이클 판별을 위해 유니온파인드 사용

2. 그래프 데이터를 가중치 기준으로 정렬하기 : 가중치 기준으로 오름차순 정렬

3. 가중치가 낮은 에지부터 연결 시도 : 대표 노드가 다르다면 연결(같으면 싸이클 생김)

4. 과정 3반복

5. 총 에지 비용 출력

 

유니온 파인드

[1717번] 집합의 표현 (유니온 파인드)

---

풀이

"""
노드의 개수 V (1~10,000)
에지의 개수 E (1~100,000)
A B C (A번 노드와 B번 노드가 가중치 C인 에지로 연결)
가중치 C (-2,147,483,648 ~ 2,147,483,648)

최소 신장 트리의 가중치 출력
"""
import sys
from queue import PriorityQueue

input = sys.stdin.readline
sys.setrecursionlimit(100000) #  재귀의 최대 깊이 설정

# 에지 정보를 저장할 우선순위 큐 (우선순위 큐를 사용해 자동 정렬)
q = PriorityQueue()

N, E = map(int, input().split())

# 유니온파인드 : 사이클 여부 확인
# 인덱스 배열 : 대표 노드 저장
arr = [0] * (N+1)
for i in range(N+1):
    arr[i] = i

# 에지 리스트
for _ in range(E):
    a, b, c = map(int, input().split())
    q.put((c, a, b))
    

def find(a):  # 대표노드 찾기
    if a == arr[a]:
        return a
    else:
        arr[a] = find(arr[a])
        return arr[a]

def union(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        arr[b] = a


# 사용 에지 수 저장 변수
useEdge = 0

# 정답 변수
result = 0

# 사용한 에지 수가 노드 수-1이 될 때 까지
while useEdge < N-1:

    # 큐에서 에지 정보 가져오기
    w, s, e = q.get()

    # 에지 시작점과 끝점의 부모 노드가 다르면 (연결해도 사이클이 생기지 않으면)
    if find(s) != find(e):
        union(s, e)
        result += w
        useEdge += 1

print(result)