(Python/🥇3)백준알고리즘 4386번: 별자리 만들기

문제 바로가기 

 

문제:

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력:

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

출력:

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

 

풀이:

오랜만에 크루스칼 문제가 풀고 싶어져서 풀었다. 까먹었을까봐..

import math
import sys
from itertools import combinations

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

# 크루스칼 알고리즘 노드가 작음
n = int(input())
parents = [i for i in range(n)]
lst = [list(map(float, sys.stdin.readline().rstrip().split(" "))) for _ in range(n)]

# 모든 점 사이 간선 구해야함.
edges = []

for i in range(n - 1):
    for j in range(i + 1, n):
        edges.append((math.sqrt((lst[i][0] - lst[j][0]) ** 2 + (lst[i][1] - lst[j][1]) ** 2), i, j))
edges.sort() # 간선 기준 오름차순
def find_parent(node):
    if parents[node] != node: # 자기자신이 부모가 아님, 부모가 있다.
        parents[node] = find_parent(parents[node]) # 부모의 부모 찾음
    return parents[node]
def union(x, y):
    x = find_parent(x)
    y = find_parent(y)
    # 작은 값이 부모
    if x < y :
        parents[y] = x
    else:
        parents[x] = y

result = 0
for edge in edges:
    e, x, y = edge
    if find_parent(x) != find_parent(y): # 부모가 다르면 사이클 형성 x
        union(x,y)
        result += e
print(round(result,2))



그 대신 이 문제는 

각 노드별 거리를 내가 직접 구하는 문제이다.

 

처음에는combinations 를 사용하려 했지만 그러면 각 노드 번호를 모른다. 그래서 그냥 포문으로 만들었다. 

별이 1000개 밖에 없어서 다행이다.