백준 1197
최소 스패닝 트리의 가중치 구하기.
- 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
- 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
- 첫째 줄에 정점의 개수 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 3 1 2 1 2 3 2 1 3 3 | 3 |
접근 방식
:
알게된 점
모든 그래프를 연결. 가중치 합이 최소가 되도록.
-> 크루스칼 알고리즘 이용.
- 가중치를 기준으로 오름차순하여 작은 가중치부터 선택
- 사이클을 이루는 지 확인(유니온 파인드 이용)
- 사이클을 이루지 않는다면 연결(루트노드를 같게)
- 가중치 더해줌
코드
def find(v):
if v == root[v]: # 본인이 대장인경우
return v
else: # 본인이 대장이 아니면 재귀적으로 대장 찾음
y = find(root[v])
root[v] = y # v의 대장을 바로 제일 위 대장인 y로 바꿔줌
return y
def union(a, b):
a = find(a)
b = find(b)
if a>b : # 더 작은 수를 루트로 만든다.
root[a] = b
else :
root[b] = a
v, e = map(int, input().split())
graph = []
for _ in range(e):
s, e, w = map(int, input().split())
graph.append((w, s, e))
graph.sort(key=lambda x : x[0]) # 비용 기준 오름차순 정렬
root = [i for i in range(v+1)] #처음 각 원소의 대장은 자기 자신
sumi = 0 # 구해야할 최종 비용
for w, s, e in graph:
if find(s) != find(e): # 대장이 서로 다르면
union(s, e) # 트리 합해줌
sumi += w
print(sumi)
