난이도 : 골드 3
유형 : 최소신장트리
문제 출처 : https://www.acmicpc.net/problem/4386
문제
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
- 별들이 2차원 평면 위에 놓여 있다.
- 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
모두 이어야 하는데 최소비용으로 이어야 한다?
-> 최소 신장 트리
입력
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
출력
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
예제 1 을 보면
3
1.0 1.0
2.0 2.0
2.0 4.0이렇게 주어져있다 이는
3개의 별이 있는데 각각 별의 좌표가 (1,1) , (2,2) , (2,4) 에 있다는 뜻이다.
그림으로 나타내면 다음과 같이 될 것 같다.
전에 풀었던 1197번과 같이 mst를 구하는 문제이지만 여기서는 간선의 가중치를 피타고라스로 내가 구해서 크루스칼 알고리즘으로 mst를 구하면 될 것 같다.
해답 및 풀이
import sys
input = sys.stdin.readline
# 유니온-파인드
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
ra, rb = find(a), find(b)
#두 대표가 같으면 이미 같은 그룹이므로 합칠 필요 없다.
if ra == rb:
return False
#랭크(트리 높이) 비교해서 작은 쪽을 큰 쪽 밑으로 붙임
if rank[ra] < rank[rb]:
parent[ra] = rb
elif rank[ra] > rank[rb]:
parent[rb] = ra
# 높이가 같은 경우 어느 쪽에 붙여도 상관없으니 한쪽을 기준으로 선택.
else:
parent[rb] = ra
rank[ra] += 1
# 합쳤음을 알림
return True
n = int(input())
stars=[]
for _ in range(n):
x, y = map(float,input().split())
stars.append((x,y))
edges = []
for i in range(n):
x1, y1 = stars[i]
for j in range(i+1, n):
x2, y2 = stars[j]
w = ((x1 - x2)**2 + (y1 - y2)**2) ** 0.5 # 거리구하기, 피타고라스의 정리
edges.append((w, i, j))
edges.sort()
parent = list(range(n))
rank = [0] * n
mst = 0.0
picked = 0
for w, a, b in edges:
if union(a,b):
mst += w
picked += 1
if picked == n - 1:
break
print(f"{mst:.2f}")++ 마지막 출력하는 곳에서
print(f"{mst:.2f}") 는 파이썬의 f-포맷팅.
중괄호 안에 변수 적고 콜론 찍고 .2f , .3f, 이런식으로 소수 몇째자리까지 출력해줄지 명시해줄 수 있다.
Frontend Engineers