[백준] 2887: 행성 터널

정렬 + MST

문제 : 행성 터널

이 문제는 딱 보고 크루스칼 알고리즘로 풀면 되겠다는 생각이 들었습니다.
그런데 n의 범위가 10만이라서 인덱스 간의 거리를 모두 추가하면 O(n^2) 이기 때문에 메모리 초과가 발생하는 문제점이 존재합니다.

그래서 이 문제의 핵심은 모든 행성을 비교하지 않고 어떻게 효율적으로 두 행성간의 거리를 입력 할 수 있을까? 입니다.

--> answer : 정렬을 통해 모든 행성을 비교하지 말고 미리 두 행성간의 가장 작은 거리를 넣어보자!

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

1. 1번 행성과 2번 행성을 연결하는데 드는 비용이 2 , 2번행성과 4번 행성을 연결하는데 드는 비용이 1라고 할게요.
   그러면 2번 4번 행성을 먼저 연결하는 것이 우선이겠죠?
   (최소비용을 구하려면 일단, 값이 작은 순서대로 더해져야 하니까요, 그리고 크루스칼 특성 상 모든 노드를 연결 하기 때문이기도 하죠)
2. 또한, 1번과 2번 행성을 연결 하는 비용은 x, y, z 중의 가장 작은 값이 되기 때문에
   (비용, 행성1, 행성2) 라고 한다면 (0, 1, 2) (2, 1, 2) 이렇게 중복될 수가 있어요
   -> min((abs(xa-xb), abs(ya-yb), abs(za-zb))
   그런데 우리가 여기서 정렬을 한다면 union_find 함수가 동작할 때 중복 여부를 확인하기 때문에 최솟값이 아닌 (2, 1, 2)는 무시되겠지요.

그래서 값을 이렇게 추가해주고 나머지는 크루스칼 알고리즘 돌리면 답을 구할 수 있습니다.

import sys
import copy
input = sys.stdin.readline
n = int(input())
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
graph = []
for i in range(n):
	x, y, z = map(int, input().split())
	graph.append([x, y, z, i])

x = copy.deepcopy(graph)
y = copy.deepcopy(graph)
z = copy.deepcopy(graph)
x.sort(key=lambda x : x[0])
y.sort(key=lambda x : x[1])
z.sort(key=lambda x : x[2])
edges = []
for i in range(len(x)-1):
	edge = (abs(x[i+1][0] - x[i][0]), x[i][-1], x[i+1][-1])
	edges.append(edge)
for i in range(len(y)-1):
	edge = (abs(y[i+1][1] - y[i][1]), y[i][-1], y[i+1][-1])
	edges.append(edge)
for i in range(len(z)-1):
	edge = (abs(z[i+1][2] - z[i][2]), z[i][-1], z[i+1][-1])
	edges.append(edge)
edges.sort()
parent = [0] * n
for i in range(n):
	parent[i] = i
answer = 0
for edge in edges:
	dist, a, b = edge
	if find_parent(parent, a) != find_parent(parent, b):
		union_parent(parent, a, b)
		answer += dist
print(answer)