[python] 4386 - 별자리 만들기

4386번: 별자리 만들기 (acmicpc.net)

4386번: 별자리 만들기

 

최소 신장 트리 문제였다.

다른 점이 있다면

간선의 가중치가 직접 주어지는 것이 아니라

좌표가 주어지고 좌표의 거리에 따른 가중치값을 직접 구해야 했다.

 

별들의 좌표를 배열에 입력받은 후

두 점 사이의 거리 공식을 이용하면 될 것 같았고

모든 점들의 거리를 구해야 하기 때문에

조합을 이용하여 케이스를 구한 후 간선과 가중치를 구해 

간선 배열에 넣어주었다.

 

그리고 나머지 부분은 크루스칼 알고리즘을 이용하여 구하였다.

 

# 4386 별자리 만들기
import math
import sys
from itertools import combinations

input = sys.stdin.readline

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]


def union(x,y):
    a = find(x)
    b = find(y)
    
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
        
n = int(input())
star=[]
parent=[i for i in range(n+1)]

for i in range(n):
    x,y= map(str, input().split())
    star.append([x,y,i+1])
    
edge=[]
for com in combinations(star, 2):
    xCost = (float(com[0][0])-float(com[1][0]))**2
    yCost = (float(com[0][1])-float(com[1][1]))**2
    edge.append((math.sqrt(xCost+yCost), com[0][2], com[1][2]))
        
edge.sort()

rst=0
for ed in edge:
    cost, x, y = ed
    if find(x) != find(y):
        union(x,y)
        rst += cost

print(round(rst, 2))

 

 

 

 

 

 

 

* 모든 코드는 github에서 관리합니다.  seinShin (SEIN SHIN) (github.com)

seinShin - Overview