[Python] 백준 - 4386 별자리 만들기

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

 

 

문제해결방법 - 

 

1. 유니온 파인드(Union Find), 프림(Prim) 알고리즘으로 구현할 수 있다.

2. 입력을 받아서 위의 함수를 이용할 수 있도록 자료구조를 만들어줘야 한다,

3. 간선 비용은 피타고라스의 정리를 이용하면 된다. 

 

 

- 유니온 파인드(Union Find)

import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
parent = [i for i in range(n+1)]
d = [0]
edge, ans = [], 0
for _ in range(n):
	a, b = map(float, input().split())
	d.append((a, b))
for i in range(1, n):
	for j in range(i+1, n+1):
		cost = ((d[i][0]-d[j][0])**2+(d[i][1]-d[j][1])**2)**0.5
		edge.append((i, j, cost))
edge.sort(key=lambda x : x[2])

def FIND(x):
	if parent[x] != x:
		parent[x] = FIND(parent[x])
	return parent[x]

def UNION(x, y):
	x = FIND(x)
	y = FIND(y)
	if x < y:
		parent[y] = x
	else:
		parent[x] = y

for i in edge:
	a, b, cost = i
	if FIND(a) != FIND(b):
		ans += cost
		UNION(a, b)
print(f"{ans:.2f}")

 

- 프림(Prim)

import sys
import heapq
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
edge, graph = [0], [[] for _ in range(n+1)]
v = [0 for _ in range(n+1)]
for _ in range(n):
	a, b = map(float, input().split())
	edge.append((a, b))
for i in range(1, n): #         1     2
	for j in range(i+1, n+1): # 23    3
		cost = ((edge[i][0]-edge[j][0])**2+(edge[i][1]-edge[j][1])**2)**0.5
		graph[i].append((cost, j))
		graph[j].append((cost, i))

def prim(start):
	q = []
	heapq.heappush(q, (0, start))
	ans, cnt = 0, 0
	while q:
		cost, idx = heapq.heappop(q)
		if v[idx] == 1:
			continue
		v[idx] = 1
		ans, cnt = ans+cost, cnt+1
		for c, next in graph[idx]:
			if v[next] == 0:
				heapq.heappush(q, (c, next))
	return ans

print(f"{prim(1):.2f}")