BOJ 1647 도시 분할 계획

https://www.acmicpc.net/problem/2887
시간 1초, 메모리 128MB

input :

• N (1 ≤ N ≤ 100,000)
• x y z (-109 ≤ x, y, z ≤ 109)

output :

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

조건 :

• 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

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

---

조건을 제대로 읽자. 어차피 간선을 만들 때 신경을 쓰는 부분은 x끼리, y끼리, z끼리이다.

이럴때 가장 짧은 길이를 만들려 한다면 자기 기준으로 가장 가까운 점들에 통로를 만들어야 한다. 이는 정렬을 통해 구할 수 있다.

당연히 10만개의 점이 있다면 모든 점을 방문하면 시간 초과가 발생한다.

정렬을 통해 방문할 수 있는, 가능한 모든 간선들을 저장한 이후에 가장 짧은 것부터 설치를 하는 것이다.

import sys

def find(node):
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]

def union(a, b):
    parent_a = find(a)
    parent_b = find(b)

    if parent_a < parent_b:
        parent[parent_b] = parent_a
    else:
        parent[parent_a] = parent_b

n = int(sys.stdin.readline())
pos, edge, parent, ans = [[], [], []], [], [i for i in range(n)], []

for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))

    for j in range(3):
        pos[j].append((temp[j], i))

for i in range(3):
    temp = sorted(pos[i])

    for j in range(1, n):
        a_cost, node_a = temp[j][0], temp[j][1]
        b_cost, node_b = temp[j - 1][0], temp[j - 1][1]

        edge.append((abs(a_cost - b_cost), node_a, node_b))

edge.sort()
idx = 0
while len(ans) < n - 1:
    cost, node_a, node_b = edge[idx]

    if find(node_a) != find(node_b):
        union(node_a, node_b)
        ans.append(cost)

    idx += 1

print(sum(ans))