고정 헤더 영역
상세 컨텐츠
본문
[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)
|
'Problem Solving > Baekjoon Online Judge' 카테고리의 다른 글
| [Baekjoon Online Judge] 백준 2887번 행성 터널(Python) (0) | 2020.06.16 |
|---|---|
| [Baekjoon Online Judge] 백준 1647번 도시 분할 계획(Python) (0) | 2020.06.16 |
| [Baekjoon Online Judge] 백준 1197번 최소 스패닝 트리(Python) (0) | 2020.06.15 |
| [Baekjoon Online Judge] 백준 4195번 친구 네트워크(Python) (0) | 2020.06.15 |
| [Baekjoon Online Judge] 백준 1865번 웜홀(Python) (0) | 2020.06.15 |
| [Baekjoon Online Judge] 백준 6118번 숨바꼭질(Python) (0) | 2020.06.15 |
댓글 영역