728x90
별자리 만들기
문제
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
입력
첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
출력
첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
최소 스패닝 트리(MST) 문제라 이번에도 Prim 알고리즘을 사용하였다.
거리는 피타고라스를 사용하였다.
import sys
input = sys.stdin.readline
N = int(input())
stars = []
for i in range(N):
stars.append(tuple(map(float,input().split())))
visit = [0] * N
INF = 10**5
dist = [INF] * N
dist[0] = 0
# 프림 알고리즘
for _ in range(N):
# 최소거리인 별 찾기
min_dist = INF
for i in range(N):
if visit[i] == 0 and min_dist > dist[i]:
u = i
min_dist = dist[i]
visit[u] = 1
# 거리를 구해서 더 짧은 거리를 갱신
for v in range(N):
# 피타고라스와 round를 통해서
now_dist = (abs(stars[u][0] - stars[v][0])**2 + abs(stars[u][1] - stars[v][1])**2)**0.5
now_dist = round(now_dist,2)
if visit[v] == 0 and dist[v] > now_dist:
dist[v] = now_dist
print(sum(dist))
'@@@ 알고리즘 > 백준 스터디' 카테고리의 다른 글
백준1477(휴게소 세우기) - 참고 해결 (0) | 2022.01.31 |
---|---|
백준 20157(화살을 쏘자!) - 해결 (0) | 2022.01.26 |
백준 17349(1루수가 누구야) - 해결 (0) | 2022.01.18 |
백준 1757(달려달려) - 해결 (0) | 2022.01.16 |
백준 1013(Contact) - 해결 (0) | 2022.01.09 |