[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 4386번 _ 별자리 만들기

https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

[문제]

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

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

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

 

[입력]

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

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

[출력]

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

 

[아이디어]

1) 처음에 그리디한 접근이 가능할거라 생각했는데, 늘 최소 거리의 점을 찾아간다고 해서 조건을 만족할 수 없는 상황이다.

2) 가능한 모든 거리를 연산해둔 채로, 짧은 거리의 간선부터 유니온-파인드를 이용해 연결되지 않은 노드면 연결하고, 이미 연결된 노드이면 pass하는 것을 반복한다.

3) 최소의 거리로 연결하기 위해서는 (n-1)개의 간선이면 충분하므로 이때 종료한다.

 

# 이러한 그리디 방식으로 풀 수 없다.
import math
from collections import deque
n=int(input())
d = []

def dist(k):
    x,y = k
    global a,b
    return math.sqrt((x-a)**2+(y-b)**2)
for _ in range(n):
    x,y = map(float,input().split())
    d.append((x,y))
ans = 0
while d:
    a,b = d.pop()
    d.sort(key = dist,reverse=True)
    if d:
        ans += dist(d[-1])
print(ans)

import math
import sys
input = sys.stdin.readline

n=int(input())
stars = []
d = list(range(n))
for _ in range(n):
    x,y = map(float,input().split())
    stars.append((x,y))
dst = []

def dist(k,t):
    x,y = k
    a,b = t
    return math.sqrt((x-a)**2+(y-b)**2)    

for i in range(n):
    for j in range(i+1,n):
        dst.append((i,j,dist(stars[i],stars[j])))   

def root(x):
    if d[x]==x:
        return x
    d[x] = root(d[x])
    return d[x]
    
def union(x,y):
    a = root(x); b = root(y) 
    if a==b:
        return
    d[b] = a

dst.sort(key = lambda x:x[2], reverse=True)
cnt = 0; ans = 0
while cnt<n and dst:
    i,j,distance = dst.pop()
    if root(i)!=root(j):
        ans += distance
        cnt+=1
        union(i,j)

print(ans)