[Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리

(Python)

(글쓴날 : 2020.06.15)

 

---

* Baekjoon Online Judge, 백준 1197번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1197번 최소 스패닝 트리

---

1) 문제

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

1197번: 최소 스패닝 트리

---

2) 풀이 과정

* 시간 복잡도 : O(E log E)

 

그래프가 주어졌을 때, 해당 그래프에서 최소 스패닝 트리의 가중치를 구하는 문제입니다.

 

저의 경우, 크루스칼 알고리즘을 적용하였고, Python을 사용했습니다.

우선, 주어지는 정보를 인접 리스트로 구현하고, 가중치를 기준으로 오름차순 정렬한 뒤, 크루스칼 알고리즘을 적용하여 최소 스패닝 트리의 가중치를 구했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def find(target):
    if disjointSet[target] == target:
        return target
    
    disjointSet[target] = find(disjointSet[target])
    return disjointSet[target]
    
 
def union(sv, dv):
    findSV = find(sv)
    findDV = find(dv)
 
    if findSV == findDV:
        return False
    
    if findSV < findDV:
        disjointSet[findDV] = findSV
    else:
        disjointSet[findSV] = findDV
    
    return True
 
 
def kruskal():
    global ans
 
    for w, sv, dv in adjList:
        if union(sv, dv):
            ans += w
 
 
V, E = map(int, input().split())
ans = 0
 
disjointSet = [x for x in range(V + 1)]
 
adjList = []
for _ in range(E):
    A, B, C = map(int, input().split())
 
    adjList.append((C, A, B))
 
adjList.sort()
 
kruskal()
 
print(ans)

---