백준_4386_별자리 만들기
문제
https://www.acmicpc.net/problem/4386
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일
www.acmicpc.net
풀이
- 최소 스패닝 트리
https://en.wikipedia.org/wiki/Minimum_spanning_tree
Minimum spanning tree - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Tree of smallest total weight through all vertices of a graph A planar graph and its minimum spanning tree. Each edge is labeled with its weight, which here is roughly proportional to
en.wikipedia.org
- Find Union
서로소 집합 자료 구조 - 위키백과, 우리 모두의 백과사전
메이크셋은 8개의 개체를 생성한다. 유니온 연산을 여러 번 수행하면 여러 집합들이 합쳐진다. 컴퓨터 과학 분야에서 서로소 집합(disjoint-set) 자료 구조, 또는 합집합-찾기(union–find) 자료 구조,
ko.wikipedia.org
1. 모든 노드별 거리 값을 구한다.
2. cost가 작은 순으로 점을 연결한다.
3. 이미 연결된 점이라면, 다시 연결하지 않는다.
코드
import sys
input = sys.stdin.readline
N = int(input().strip())
starInfo = [list(map(float, input().strip().split())) for i in range(N)]
# edges별 거리 계산하기
def getValue(i, j) :
dx = starInfo[i][0]-starInfo[j][0]
dy = starInfo[i][1]-starInfo[j][1]
return (dx**2+dy**2)**0.5
edges = list()
for i in range(N) :
for j in range(i+1, N) :
value = getValue(i, j)
edges.append((value, i, j))
edges.sort()
# find union
parent = [i for i in range(len(starInfo))]
def union(i, j) :
if i==j : return
i = find(i)
j = find(j)
if i>j : parent[i] = j
else : parent[j] = i
def find(i) :
if i==parent[i] : return i
parent[i] = find(parent[i])
return parent[i]
# calculate
answer = 0
for cost, i, j in edges :
if find(i) != find(j) :
union(i, j)
answer += cost
print(round(answer, 2))