[BOJ/Python] 1197_최소 스패닝 트리

문제 출처:https://www.acmicpc.net/problem/1197

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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

예제 입력 1

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1

3

---

풀이

 

최소 스패닝 트리는 V개의 정점이 존재할 때, 가중치의 합을 최소로 하여 모든 정점을 연결한 트리이다.

크루스칼 알고리즘을 이용하여 문제를 해결하였다.

1. 정점 A에서 정점 B까지의 가중치가 C라고 하자.
2. 가중치를 기준으로 오름차순으로 정렬한다.
3. 제일 가중치가 작은 간선부터 하나씩 살펴본다.
4. 만약 현재 간선을 연결하였을 때 사이클이 생기지 않는다면 연결한다. (union & find를 이용하여 확인한다.)
5. 이 과정을 모든 간선에 대하여 수행한다.

혹은 V개의 정점이 존재할 때, 최종적으로 완성된 트리의 간선의 개수는 V-1개가 되므로 V-1개의 간선을 연결한다면 탐색을 종료해도 된다.

가중치를 기준으로 오름차순으로 정렬하였으므로 이후에 나오는 간선들의 가중치는 현재 연결되어 있는 간선들의 가중치보다 크고, 따라서 현재 연결되어 있는 간선들의 가중치의 합보다 더 작은 트리는 만들 수 없다.

 

코드는 다음과 같다.

 

import sys
 
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
 
 
v,e = map(int,sys.stdin.readline().split())
edge = []
parent = [i for i in range(v+1)]
 
for _ in range(e):
    a,b,c = map(int,sys.stdin.readline().split())
    edge.append((c,a,b))
 
edge.sort()
 
result = 0
for c,a,b in edge:
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result+=c
 
print(result)

• find_parent 함수를 이용하여 A노드와 B노드가 현재 같은 집합에 속해있는지 확인한다.
• 만약 두 노드가 같은 집합에 속해 있다면, 두 노드를 연결할 경우 사이클이 발생하게 되므로 안된다.
• 만약 같은 집합에 속해 있지 않다면 union_parent 함수를 이용하여 연결하고, result에 가중치 c를 더해준다.
• 최종적으로 result는 최소 스패닝 트리의 가중치의 합이므로 이를 출력한다.