행성터널

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

2887번: 행성 터널

문제요약;

행성의 x,y,z좌표가 주어지고 각 행성간 거리는 서로의 좌표의 차이중 가장 짧은 것을 기준으로 한다.

모든 행성을 연결할 가장 짧은 엣지 합은?

플레5

 

소요시간:

30분

 

1차 시도:

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
	x,y,z = map(int,input().split())
	arr.append((x,y,z,i))

#모든행성을 터널로 연갈하는 데 최소비용? > 크루스칼 사용
parent = [i for i in range(n+1)]

#크루스칼
def find(parent,x):
	if parent[x] !=x:
		parent[x] = find(parent,parent[x])
	return parent[x]

def union(parent,x,y):
	y = find(parent,y)
	x = find(parent,x)

	if y>x:
		parent[y] =x
	else:
		parent[x] =y

#크루스칼을 하되, 전체 다 할 수 없으므로, x,y,z기준으로 sorted한후 바로 앞뒤(제일짧은)사이 거리넣기
dist = []
ans = 0
for i in range(3):
	arr.sort(key = lambda x : x[i])
	for j in range(n-1):
		dist.append((arr[j+1][i]-arr[j][i],arr[j+1][3],arr[j][3]))

dist.sort()
num = 0
#그후 크루스칼 이때 다 연결 했다면 미리 나오기
for l,j,i in dist:
	if find(parent,j) != find(parent,i):
		union(parent,j,i)
		ans +=l
		num +=1
		if num == n-1:
			break
print(ans)