[🥇4 / 백준 4386 / 파이썬] 별자리 만들기

 

4386번: 별자리 만들기

 

문제

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

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

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

입력

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

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

출력

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

 

예제 입력  3 1.0 1.0 2.0 2.0 2.0 4.0

예제 출력  3.41

 

풀이

 

간선이 주어지지 않기 때문에 입력받은 좌표를 통해 간선을 직접 만들어주어야 한다.

정점의 번호는 입력받은 순서대로 0, 1, … n-1 이라고 하자.

 

해당 정점부터 다른 각각의 모든 정점들까지의 간선을 전부 만들어주어야 한다.

따라서 간선의 개수는 N²이 되며, 시간 복잡도도 O(N²)이다.

별의 개수가 100개 밖에 안되기 때문에 부담없이 코드를 작성하면 된다.

 

 

이제 간선이 모두 만들어졌기 때문에 프림, 혹은 크루스칼 알고리즘 중에 편한 것을 선택하여 진행한다.

필자는 저번에 크루스칼을 했기 때문에 이번 문제에선 프림 알고리즘을 선택하여 풀었다.

 

최소 힙을 이용하여 구현했기 때문에 O(E log V) 안에 문제 해결이 가능하다.

(E = 간선의 개수, V = 정점의 개수)

 

import sys, heapq
input = sys.stdin.readline

def dist(x1,y1,x2,y2):
    return ((x2-x1)**2+(y2-y1)**2)**0.5

n = int(input())
pos = [tuple(map(float,input().split())) for _ in range(n)]
# 인접 리스트 생성
link = [[] for _ in range(n)]
for i in range(n):
    x1,y1 = pos[i]
    for j in range(n):
        if i==j:
            continue
        x2,y2 = pos[j]
        link[i].append((j,dist(x1,y1,x2,y2)))

# Prim
visit = [False] * n
hq = [(0,0)]
cnt,ans = n,0
while cnt:
    curDist,curNode = heapq.heappop(hq)
    if visit[curNode]:
        continue
    
    cnt -= 1
    visit[curNode] = True
    ans += curDist
    for toNode,toDist in link[curNode]:
        if visit[toNode]:
            continue
        heapq.heappush(hq,(toDist,toNode))
print(ans)