2887 행성 터널

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

 

 

크루스칼 알고리즘을 쓰면된다.

하지만 여기서 간선이 주어지지 않기 때문에 간선을 알아서 생성해내야한다.

 

그래서 0,0,0 지점과의 거리 별로 정렬, 중앙점과의 거리별로 정렬, x,y,z 값을 기준으로 정렬...

내 머리로 할 수 있는 간선 생성 방법을 모두 해본것같다.

그래도 계속 틀려서 답을 봤는데

 

x를 기준으로 정렬한다음 간선을 추가

y를 기준으로 정렬한다음 간선을 추가

z를 기준으로 정렬한다음 간선을 추가

그리고 간선을 가중치를 기준으로 오름차순 정렬

 

을 하고 크루스칼알고리즘을 사용하는 것이었다. 

 

 

import sys
input = sys.stdin.readline

n = int(input().rstrip())
answer = 0
info = []
for i in range(n):
  x,y,z = map(int, input().rstrip().split(" "))
  info.append( (x,y,z,i+1) )

graph = []
# 부모 리스트
parents = [0] * (n+1)

# 부모를 자기자신으로 초기화
for i in range(n+1):
  parents[i]=i

# 최종 부모노드를 찾는 함수
def get_root_node(x):
  global parents
  if( parents[x] != x ):
    parents[x] = get_root_node(parents[x])
  return parents[x]

# union
def union(a,b):
  global parents
  a = get_root_node(a)
  b = get_root_node(b)
  if(a<b):
    parents[b] = a
  else:
    parents[a] = b

info = sorted(info, key=lambda x: x[0])
for i in range(0,n-1):
  graph.append( (info[i][3], info[i+1][3], abs(info[i][0] - info[i+1][0]) ) )
info = sorted(info, key=lambda x: x[1])
for i in range(0,n-1):
  graph.append( (info[i][3], info[i+1][3], abs(info[i][1] - info[i+1][1]) ))
info = sorted(info, key=lambda x: x[2])
for i in range(0,n-1):
  graph.append( (info[i][3], info[i+1][3], abs(info[i][2] - info[i+1][2]) ) )

graph = sorted(graph, key=lambda x:x[2])

for edge in graph:
  a,b,c = edge
  if( get_root_node(a) != get_root_node(b) ):
    union(a,b)
    answer+=c
print(answer)