[Python] Kruskal - 2287. 행성터널[플5]

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

2887번: 행성 터널

 

>> 문제 핵심 포인트

-n개의 행성간의 nC2 조합을 만들어 거리 구하기-> 메모리 초과

- 결국 cost로 주어진 |x1-x2|, |y1-y2|, |z1-z2|를 cost로 하여 각각의 간격을 넣어주어야 함 3(n-1)번만큼

- 가까운 행성별 정렬이 중요

=> 이걸 문제를 보고 바로 떠올릴 수 있을까?

 

def find_parent(parent, x):

  if parent[x] !=x:

    parent[x]= find_parent(parent, parent[x])

  return parent[x]

def union_parent(parent, a,b):

  a= find_parent(parent, a)

  b= find_parent(parent, b)

  if a<b:

    parent[b]=a

  else:

    parent[a]=b

v= int(input())

parent= [0]* (v+1)

for i in range(0, v+1):

  parent[i]=i

#좌표정보 입력받기

x=[]

y=[]

z=[]

for i in range(1, v+1):

  x1,y1,z1= map(int, input().split())

  x.append((x1,i))

  y.append((y1,i))

  z.append((z1,i))

x.sort()

y.sort()

z.sort()

#각 연결 정보 생성하기

edges=[]

for i in range(v-1):

  #cost, a, b

  edges.append((x[i+1][0]- x[i][0], x[i][1], x[i+1][1]))

  edges.append((y[i+1][0]- y[i][0], y[i][1], y[i+1][1]))

  edges.append((z[i+1][0]- z[i][0], z[i][1], z[i+1][1]))

#연결하기

cnt=0

result=0

edges.sort()

for edge in edges:

  cost, a,b = edge

  if find_parent(parent, a) != find_parent(parent,b):

    union_parent(parent, a,b)

    result +=cost

    cnt+=1

  if cnt==v-1:

    break

print(result)