백준 4386 별자리 만들기 (파이썬)

접근방식

1197번과 다르게 가중치 계산(좌표 거리 계산)을 직접해야하는 최소 신장 트리 카테고리 문제였다.
1197번과 동일한 크루스칼 알고리즘 을 사용하였고 가중치를 계산하는 부분만 추가하였다.
별 간 거리 계산(가중치 계산) 부분을 제외하고 1197번 코드와 동일하다.

파이썬 코드

import sys
import math

# 크루스칼 알고리즘
# 1197번에서 가중치 계산만 추가

n = int(sys.stdin.readline())
location = []
arr=[]
for _ in range(n):
    x, y = map(float, sys.stdin.readline().split())
    location.append((x,y))

# 별 간 거리 계산 (가중치)
for i in range(n-1):
    for j in range(i,n):
        dis = round(math.sqrt((location[i][0] - location[j][0]) ** 2 + (location[i][1] - location[j][1]) ** 2),2)
        if i == j:  # 자신으로 가는 거리는 계산하지않음
            continue
        # 양방향 저장
        arr.append((dis,i,j))
        arr.append((dis,j,i))


arr.sort(key=lambda x: x[0])
parent = list(range(n + 1))

#유니온 파인드 연산
def union(a, b):
    a = find(a)
    b = find(b)

    if b < a:
        parent[a] = b
    else:
        parent[b] = a
def find(a):
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])  # 경로 압축
    return parent[a]

sum = 0
for c, a, b in arr:
    if find(a) != find(b):
        union(a, b)
        sum += c

print(sum)

접근방식

파이썬 코드

Share this post