1. 문제 설명

Moocast

2. 문제 분석

간선을 좌표 계산을 통해 직접 입력해 푸는 MST 문제. 특징은 MST 전체 비용이 아니라 MST 구성 간선 중 가장 큰 값을 리턴하는 것.

3. 나의 풀이

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
positions = []
for idx in range(n):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    positions.append([x, y, idx])
parents = [i for i in range(n)]
pq = []

def get_distance(x1, y1, x2, y2):
    return ((x1-x2)**2 + (y1-y2)**2)

def find(node):
    if parents[node] == node: return node
    else:
        parents[node] = find(parents[node])
        return parents[node]

def union(node1, node2):
    root1, root2 = find(node1), find(node2)
    if root1 == root2: return False
    else:
        parents[root2] = root1
        return True

def Kruskal():
    edge_cnt = 0
    while pq:
        cost, node1, node2 = heapq.heappop(pq)
        if union(node1, node2):
            edge_cnt += 1
            if edge_cnt == n-1: return cost
    return -1

for i in range(n):
    x1, y1, node1 = positions[i]
    for j in range(i+1, n):
        x2, y2, node2 = positions[j]
        cost = get_distance(x1, y1, x2, y2)
        heapq.heappush(pq, [cost, node1, node2])

answer = Kruskal()
print(answer)