[문제 바로가기] https://www.acmicpc.net/problem/4386
📌문제 설명
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
입력
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
출력
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
💡 문제 풀이
최소 신장 트리(MST : Minimum Spanning Tree)를 구하는 문제다.
문제에서 좌표만 주어지고 비용이 주어지지 않아서 어떻게 MST를 만들까 고민하였는데
별의 개수가 100개 이하로 큰 편이 아니기 때문에 모든 별들의 거리를 구하여 (거리, 별1, 별2) 형태의 자료를 heap에다 넣어 MST를 만들었다.
MST는 크루스칼(Kruskal) 알고리즘으로 구현하였다.
크루스칼 알고리즘은 부모노드를 찾는 함수(find_parent)와 노드를 서로 연결시키는 함수(union_parent)만 구현하면 해결할 수 있다.
코드는 다음과 같다.
import sys, heapq
def calculate(x1, y1, x2, y2):
return ((x1-x2) ** 2 + (y1-y2) ** 2) ** (0.5)
def find_parent(start):
if start != parent[start]:
return find_parent(parent[start])
return parent[start]
def union_parent(star1, star2):
star1 = find_parent(star1)
star2 = find_parent(star2)
if star1 < star2:
parent[star2] = star1
else:
parent[star1] = star2
n = int(input())
stars = []
for _ in range(n):
x, y = map(float, input().split())
stars.append((x, y))
parent = [i for i in range(n)]
costs = []
answer = 0
for i in range(n-1):
for j in range(i+1, n):
heapq.heappush(costs, (calculate(stars[i][0], stars[i][1], stars[j][0], stars[j][1]), i, j))
while costs:
cost, i, j = heapq.heappop(costs)
if find_parent(i) != find_parent(j):
union_parent(i, j)
answer += cost
print(round(answer, 2))
MST를 만드는 알고리즘으로 프림(Prim)알고리즘이 있다.
프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘인데, 이 문제의 경우 간선이 아닌 정점(좌표)이 주어졌기 때문에 프림(Prim)알고리즘을 사용하는 것이 더 올바른 방법인 것 같다.
※ 결론 : 프림(Prim)알고리즘 공부하자 😊
