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

---

출력

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

입/출력

---

풀이

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,input().split())
parent = [0]*(v+1)

result = 0
edge = []

for i in range(1,v+1):
    parent[i] = i

for _ in range(e):
    a,b,cost = map(int,input().split())
    edge.append((cost,a,b))

edge.sort()

for e in edge:
    cost,a,b = e
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result += cost
print(result)​

결과

---

문제 풀이

1. find_parent 함수로 특정 원소가 속한 집합을 찾는다.
2. union_parent 함수로 두 원소가 속한 집합을 합친다.
3. v, e로 노드와 간선의 개수를 입력받는다.
4. 모든 간선을 담을 리스트와 최종 결과를  출력할 edge, result를 선언한다.
5. parent 배열을 자기 자신으로 초기화한다.
6. 모든 간선에 대해서 a, b, cost를 입력받은 후 edge 배열에 튜플의 첫 번째 원소를 비용으로 설정한다.
7. 간선을 비용 순으로 정렬한다.
8. 간선을 하나씩 확인하며 사이클이 발생하지 않을 경우 간선을 합친 후 result에 비용을 추가한다.