[Python] BOJ 4386번. 별자리 만들기

작성일 | In |

4386번. 도시 분할 계획

문제 링크

풀이 코드

  • 전형적인 MST 문제입니다.
  • 입력이 시작점,끝점,비용으로 주어지는 대신, 점들의 좌표로 주어집니다.
  • 먼저 좌표를 다 받은 다음 (시작점, 끝점, 비용)을 만들어서 edge에 넣어주면 됩니다.
  • 그 뒤에는 소수점만 신경쓰며 MST로 뚝딱! EASY~
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
# 4386번. 별자리 만들기


import math
def make(parent):
    for i in range(v + 1):
        parent[i] = i
    return parent


def find(parent, a):
    if parent[a] == a:
        return a
    parent[a] = find(parent, parent[a])
    return parent[a]


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a > b:
        parent[a] = b
        return True
    elif a < b:
        parent[b] = a
        return True
    return False

n = int(input())
# 별들의 좌표를 넣어준다.
stars = []
for i in range(n):
    x,y = map(float,input().split())
    stars.append([x,y])
# MST 활용을 위해 (거리,시작,끝)을 만든다.
parent = [i for i in range(n+1)]
edges = []
for i in range(n-1):
    for j in range(i+1,n):
        start = stars[i]
        end = stars[j]
        distance = math.sqrt((start[0]-end[0])**2 + (start[1]-end[1])**2)
        edges.append([distance,i,j])
edges.sort()

cnt, ans = 0,0
# U-F
for edge in edges:
    if union(parent, edge[1], edge[2]):
        ans += edge[0]
        cnt += 1
        if cnt == n - 1:
            break

print(round(ans,2))

비고