[이코테] CH10 그래프 이론 실전문제 44번 행성 터널

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

문제

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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

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

예제 입력 1 복사

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

예제 출력 1 복사

4

 

처음에 접근한 방법

1. 간선이 없네... 거리를 직접 구해볼까? 모든 노드를 연결하고 거기서 최소신장트리를 만들자!

2. 아니야.. 그러면 N^2번 돌아서 시간복잡도에 걸릴 거니까 한번 후보들을 추려보자

3. 행마다 후보를 하나씩 정하면 시간복잡도가 조금은 줄지 않을까?하는 행복함에 열심히 돌려봤지만 

ㅋㅋ 역시나 3%에서 시간 초과

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def d(x,y):
    if x < y:
        return y-x
    else:
        return x-y
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

N = int(input())
edges = []
parent = [0] * (N)
for i in range(N):
    parent[i] = i
for _ in range(N):
    x,y,z = map(int,sys.stdin.readline().split())
    edges.append((x,y,z))
    
cost = [[0 for _ in range(N)] for _ in range(N)] 

edge = [] 
num = list(itertools.combinations(parent,2))
minarr = copy.deepcopy(cost)
minindex = []
for i in range(N):
    minarr[i].sort()
    count = minarr[i].count(0)
    minindex.append(minarr[i][count])
   
index = 0
for i in range(N):
    for j in range(N):
        count = minarr[i].count(0)
        if (cost[i][j] <= minindex[index] and i!=j) and count >=2:
            edge.append((min(d(edges[i][0],edges[j][0]),d(edges[i][1],edges[j][1]),d(edges[i][2],edges[j][2])),i,j))
        elif count == 1:
            edge.append(0,i,j)
    index +=1
sum = 0

edge.sort()

for realedge in edge:
    realcost,a,b = realedge
    if find_parent(parent,a)!=find_parent(parent,b):
        union_parent(parent,a,b)
        sum += realcost
print(sum)

이게 처음 휘뚜루마뚜루 코드다

행마다 후보 하나씩을 정해서 최소신장트리를 만들려는 나의 계획이

처참하게 무너진 것이다 ! 

그래서 ,, x,y,z 별로 나눠서 edge를 Sort해줘야 시간복잡도가 O(V)가 나오게 되면서 해결이 가능해진다..

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9
def d(x,y):
    if x < y:
        return y-x
    else:
        return x-y
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

N = int(input())
edges = []
parent = [0] * (N+1)
x = []
y = []
z = []
for i in range(1,N+1):
    parent[i] = i
for i in range(1,N+1):
    data = list(map(int,sys.stdin.readline().split()))
    x.append((data[0],i))
    y.append((data[1],i))
    z.append((data[2],i)) # 각 좌표별로 받고 , 좌표순대로 정렬 실시

x.sort()
y.sort()
z.sort()
for i in range(N-1):
    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]))
edges.sort() # 처음엔 이게 어떻게 굴러갈까 했는데 정렬하면서 먼저 최소신장트리를 완성한다
sum = 0
for edge in edges:
    cost,a,b = edge
    if find_parent(parent,a)!=find_parent(parent,b): # 사이클 발생 X인 경우에만 서로소 집합을 합쳐준다
        union_parent(parent,a,b)
        sum += cost
print(sum)