[백준] 1197 최소 스패닝 트리

1197 최소 스패닝 트리

📄Description

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

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

입력 조건

• 첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력 조건

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

예제 입력

input	output
3 3 1 2 1 2 3 2 1 3 3	3

---

🤔생각 정리

1. 크루스칼 알고리즘을 사용해서 최소 스패닝 트리를 찾으면 되겠네.
2. a, b, c가 주어지면 a와 b를 연결하는 간선의 가중치가 c가 되겠네.

💡Pseudo Code💡

1. v, e: 정점 수, 간선 수
2. a, b, c: 간선 (a,b)의 가중치는 c
3. 간선 리스트에 (c, a, b) 추가하기
4. 간선리스트 오름차순 정렬하기
5. 순환성이 생기지 않도록 최소 간선 선택하며 추가하기
6. return 가중치의 합

---

🖥️코드화

import sys

# 정점이 속한 집합 찾기
def find(p, v):
    if p[v] == v:
        return v
    return find(p, p[v])

# 두 정점의 집합 합치기
def union(p, a, b):
    p1 = find(p, a)
    p2 = find(p, b)
    if p1 < p2:
        p[p2] = p1
    else:
        p[p1] = p2

v, e = map(int, sys.stdin.readline().split())
edge = []
for j in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    edge.append((c,a,b))
    
# 크루스칼 알고리즘
edge.sort() ## 간선 오름차순 정렬
p, w = list(range(v+1)), 0
for c, a, b in edge:
    if find(p,a) != find(p,b): ## 부모 정점이 다르다면
        union(p,a,b) ## 간선 추가하기
        w += c
print(w)