Q44. 행성 터널
2887번: 행성 터널
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이
www.acmicpc.net
드디어 채점가능한 문제를 만났넼ㅋㅋ ㅌㅋㅋㅋㅋㅋ
함 풀어보자잉!
이것도 소리치네
"최소신장트리 써주세요!!!"
다만 좌표계가 2차원에서 3차원으로 확장되고 각 vertex 사이의 거리를 내가 직접 구해줘야된다는.. 약간의 응용력이 필요한 문제인거같다.
각 vertex 사이 거리 구하는데에 O(N^2), 그걸로 min spanning tree 구하는데에 O(N log N) 해서 총 O(N^2) 나올듯?
어 근데 보니까 N이 최대 10만이네..? N^2으로 안될텐데 그러면..
흠?
어.. 발상이 막혔다.
O(N^2)보다 빠르게 행성 사이의 거리를 구하려면 어떻게 해야될까;;
뭔가 감으로는 O(N^2)보다 빨라야되니까 O(N log N)일거고 x,y,z 기준으로 각각 정렬해야될거같은 삘이 강하게 드는데 그 다음을 모르겠단 말이지.
결국 정답을 봤는데 내 발상은 맞았고 거기서 조금 더 나아가기만 하면 됐다. 근데 가슴으로 와닿진 않음. 뭔가 '아 그래 상식적으로 이렇게 될수밖에 없지'가 아니라 '어.. 이렇게 될거같긴 하네 ㅇㅇ 근데 왜 이게 최적해인거지?'싶은?
일단 해보자!
######### input ##########
N = int(input())
X = []
Y = []
Z = []
for i in range(N):
x, y, z = map(int, input().split())
X.append((x, i))
Y.append((y, i))
Z.append((z, i))
###########################
##### prepare edge list #####
edges = []
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()
#############################
##### union-find #####
parent = [i for i in range(N)]
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, x, y):
p1 = find(parent, x)
p2 = find(parent, y)
parent[max(p1,p2)] = min(p1,p2)
######################
####### main #########
mincost = 0
for dist, v1, v2 in edges:
if find(parent, v1) != find(parent, v2):
union(parent, v1, v2)
mincost += dist
print(mincost)
######################
신기하네 이걸 이렇게 풀 생각을 하다니.
문제 만드는 사람들이나 푸는 사람들이나 대단하다.
이게 백준 골드 상위권 문제구나.