[백준 파이썬] 1197번 최소 스패닝 트리 (골드 4)

1197번 최소 스패닝 트리 (골드 4)

1. 문제
그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 
그 가중치의 합이 최소인 트리를 말한다.

2. 입력
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 
다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 
이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. 
C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 
최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 
2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

3. 출력
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

4. 문제 풀이
모두 연결되어 있는 것은 확정 → 이미 연결 그래프
가중치 최소로 전체 연결 → MST 문제
간선이 100,000개 → O(E log E) 가능
→ Kruskal 사용

<<Kruskal 알고리즘>>
탐욕적 방법을 이용하여 가중치를 간선에 할당한 그래프의 모든 정점을 
최소비용으로 연결하는 최적 해답을 구하는 것

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

1) 그래프의 간선들을 가중치의 오름차순으로 정렬
2) 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택
3) 해당 간선을 현재의 MST (최소비용신장트리)의 집합에 추가한다.

>>>코드

"""
1197번 최소 스패닝 트리 (골드 4)
input : 
    v 정점의 개수, e 간선의 개수
    a, b, c 간선의 연결점과 가중치
output :
    w 스패닝 트리의 가중치
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

v, e = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(e)]

edge.sort(key = lambda x : x[-1])
group = [i for i in range(v+1)]

def find(num):
    if num != group[num]:
        group[num] = find(group[num])
    return group[num]

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

length = 0
for a, b, c in edge:
    if find(a) != find(b):
        union(a, b)
        length += c

print(length)

5. 문제 링크
https://www.acmicpc.net/problem/1197