[백준 BOJ / Python] 4386번 별자리 만들기

문제

두 별 사이의 거리만큼 별자리를 만는 비용이 든다고 할 때,

n개의 별들을 이어 별자리를 만드는 최소 비용을 구하는 문제이다.

별자리의 조건

• 두 별 사이의 거리는 서로 다른 두 별을 일직선으로 이은 선의 길이와 같다.
• 모든 별은 직/간접적으로 연결되어 있다.

풀이

• 두 별 사이의 거리를 가중치로 두고, 크루스칼 알고리즘을 이용하여 최소 비용을 구한다.
• 직각 삼각형의 대각선의 길이를 구하는 공식을 이용하여 가중치를 구한다.
  $c^2 = a^2 + b^2 $
  $c = \sqrt{{a}^2 + {b}^2}$
  $c = \sqrt{(x1-x2)^2 + (y1-y2)^2}$

• 가중치와 두 별의 번호를 간선 list 에 저장한다.
• 가중치를 기준으로 오름차순으로 간선 list를 정렬한다.
• 작은 가중치부터 순서대로 별들을 연결한다. (부모 노드를 union-find 알고리즘을 활용해 연결한다.)

Python 코드

import sys
input = sys.stdin.readline

# Union-Find 알고리즘
def find(x):
    if x == parent[x]:
        return x
    parent[x] = find(parent[x])
    return parent[x]
def union(x,y):
    x = find(x)
    y = find(y)

    if x <= y:
        parent[y] = x
    else:
        parent[x] = y

# 거리 계산
def dist(star1,star2):
    x1,y1 = star1
    x2,y2 = star2
    return round(((x1-x2)**2+(y1-y2)**2)**0.5, 2)

n = int(input())
nodes = [list(map(float,input().split())) for _ in range(n)]
edges = []
parent = list(range(n))
res = 0
for i in range(n):
    for j in range(i+1,n):
        d = dist(nodes[i],nodes[j])
        edges.append((d,i,j))
        
# 간선을 최소 비용 순으로 정렬
edges.sort(key = lambda x: x[0])

for i in range(len(edges)):
    d,x,y = edges[i]
    if find(x) != find(y): # 부모가 다르면
        union(x,y) # 최소 신장트리에 포함시킴
        res += d

print(res)

 

문제출처

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

 

최소신장트리 크루스칼 알고리즘

[알고리즘 / Python] 최소신장트리 (크루스칼 알고리즘)