[백준] 행성 터널

www.acmicpc.net/problem/2887

2887번: 행성 터널

 

import sys

def find_parent(i):
    if parent[i]!=i:
        parent[i]=find_parent(parent[i])
    return parent[i]

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

    if a==b:
        return False

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

def kruskal(edges):
    result=0

    for cost,a,b in edges:
        if union(a,b):
            result+=cost


    return result

input=sys.stdin.readline

n=int(input())

parent=[i for i in range(n)]

l_x=[]
l_y=[]
l_z=[]

for i in range(n):
    x,y,z=map(int, input().split())
    l_x.append((x, i))
    l_y.append((y, i))
    l_z.append((z, i))

l_x.sort()
l_y.sort()
l_z.sort()

edges=[]

for i in range(n-1):
    edges.append((abs(l_x[i][0]-l_x[i+1][0]), l_x[i][1], l_x[i+1][1]))
    edges.append((abs(l_y[i][0]-l_y[i+1][0]), l_y[i][1], l_y[i+1][1]))
    edges.append((abs(l_z[i][0]-l_z[i+1][0]), l_z[i][1], l_z[i+1][1]))

edges.sort()

result = kruskal(edges)
print(result)