백준 5719 : 문제링크
문제유형 :
- 그래프
- 크루스칼 알고리즘
설명
- 정점의 개수 N이 최대 1000이므로, 가능한 통로의 개수는 약 N^2이다
- 크루스칼 알고리즘은 간선의 개수가 E일 때 O(ElogE)로 동작하므로 해결할 수 있다 (정렬 알고리즘 시간복잡도)
풀이
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
52
53
54
55
56
57
58
59
60
61
62import math
import sys
input = sys.stdin.readline
def get_distance(p1, p2):
a = p1[0] - p2[0]
b = p1[1] - p2[1]
return math.sqrt((a * a) + (b * b))
def get_parent(parent, n):
if parent[n] == n:
return n
return get_parent(parent, parent[n])
def union_parent(parent, a, b):
a = get_parent(parent, a)
b = get_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def find_parent(parent, a, b):
a = get_parent(parent, a)
b = get_parent(parent, b)
if a == b:
return True
else:
return False
edges = []
parent = {}
locations = []
n, m = map(int, input().split())
for _ in range(n):
x, y = map(int, input().split())
locations.append((x, y))
length = len(locations)
for i in range(length - 1)
for j in range(i + 1, length):
edges.append((i + 1, j + 1), get_distance(location[i], location[j]))
for i in range(1, n + 1):
parent[i] = i
for i in range(m):
a, b = map(int, input().split())
union_parent(parent, a, b)
edges.sort(key=lambda data: data[2])
result = 0
for a, b, cost in edges:
if not find_parent(parent, a, b):
union_parent(parent, a, b)
result += cost
print("%0.2f" %result)