[Baekjoon] 4386번 : 별자리 만들기

1. 문제

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

• Union-Find, 최소 신장 트리 문제

// 문제
도현이는 우주의 신이다. 
이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 
별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 
선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 
별자리를 만드는 최소 비용을 구하시오.

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

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

// 예제 입력 1 
3
1.0 1.0
2.0 2.0
2.0 4.0

// 예제 출력 1 
3.41

2. 핵심 아이디어

• 모든 별들 간의 거리 계산
• 간선을 오름차순 정렬
• 두 노드의 부모를 비교하여 다르면 노드를 연결

3. Python 문제풀이

import math
import sys
input = sys.stdin.readline

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

def union(a, b) :
  a = find(a)
  b = find(b)

  if a < b :
    parent[b] = a
  else:
    parent[a] = b

n = int(input())
parent = [i for i in range(n+1)]
s = []
e = []
result = 0

for _ in range(n) :
  x, y = map(float, input().split())
  s.append((x, y))

for i in range(n-1) :
  for j in range(i+1, n) :
    e.append((math.sqrt((s[i][0] - s[j][0])**2 + (s[i][1] - s[j][1])**2), i, j))

e.sort()

for edge in e :
  cost, x, y = edge

  if find(x) != find(y) :
    union(x, y)
    result += cost

print(round(result, 2))

4. Java 문제풀이