BOJ 4386 별자리 만들기

https://www.acmicpc.net/problem/4386
시간 1초, 메모리 128MB

input :

• N (1 ≤ N ≤ 100)
• n개의 줄에 걸쳐 각 별의 x, y좌표

output :

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

조건 :

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.

• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

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

---

문제 조건의 2, 3번째의 문구를 통해 MST를 확인해야 함을 알 수 있다.

용량

문제의 제한 용량이 128MB이다. 만약 모든 edge들을 저장하려 할 때 최대로 얻을 수 있는 것은 99 * 100개의 edge를 저장해야 한다.

이를 바이트로 바꾸면 99 * 100 * 4 인데 128MB보다는 작으니 이걸 다 확인해도 될 것같다.

시간

시간 제한의 경우에도 끽해봐야 20만번의 반복인데 이 정도는 가능 할 것이다.

고로 나는 완전탐색의 방식을 선택했다.

1. 모든 노드를 확인하며 가능한 edge를 만든다.
2. 최단 거리의 노드 2개 부터 찾아서 parent를 동일하게 만들어 가도록 하였다.
3. ans를 계속 기록하게 하며 이미 연결된 노드는 연결하지 않도록 한다.
   이외에는 find, union을 사용한 것 밖에는 적을 게 없는 것 같다.

from heapq import heappop, heappush
import sys
import math

def find(node):
    if parent[node] == node:
        return parent[node]
    return find(parent[node])

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

    if parent_a < parent_b:
        parent[parent_b] = parent_a
    else:
        parent[parent_a] = parent_b

n = int(sys.stdin.readline())
data = []
edge = []
parent = [i for i in range(n)]
for i in range(n):
    x, y = map(float, sys.stdin.readline().split())

    for j in range(len(data)):
        a, b = data[j]
        heappush(edge, (math.sqrt((a - x) ** 2 + (b - y) ** 2), i, j))

    data.append((x, y))

ans = 0
while edge:
    val, a, b = heappop(edge)
    temp_a = find(a)
    temp_b = find(b)

    if temp_a == temp_b:
        continue

    union(a, b)
    ans += val

print(ans)