상세 컨텐츠

본문 제목

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

Problem Solving/Baekjoon Online Judge

by HelloMinchan 2020. 6. 15. 23:12

본문

© 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번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 �

www.acmicpc.net


2) 풀이 과정

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

 

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

 

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

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


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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)

 

관련글 더보기

댓글 영역