[ 백준 ][ 플레5 ] 2887번 - 행성 터널 ( 파이썬 Python )

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

2887번: 행성 터널

 

코드

---

import sys
input = sys.stdin.readline

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

n = int(input())
xlst, ylst, zlst = [],[],[]
for i in range(n):
    x,y,z = map(int,input().split())
    xlst.append((x, i))
    ylst.append((y, i))
    zlst.append((z, i))

xlst.sort()
ylst.sort()
zlst.sort()

edges = []
for lst in (xlst,ylst,zlst):
    for i in range(n-1):
        w1, a = lst[i]
        w2, b = lst[i+1]
        edges.append((abs(w1-w2),a,b))
edges.sort()

parent = [i for i in range(n)]
ans = 0
for w,a,b in edges:
    a, b = find(a),find(b)
    if a != b:
        if a > b:
            a,b = b,a
        parent[b] = a
        ans += w

print(ans)

 

풀이

---

행성들의 mst를 구하기 위해서는 모든 행성들간의 거리를 구해야 한다.
하지만 N이 10만까지 올라가기 떄문에 모든 행성을 비교하게 되면 시간복잡도가 O(n*n)으로 시간초과가 나게 된다.

 

따라서 행성들간의 거리를 구하는 방법으로 다른 방법을 찾아야 한다. 이 때, 우리는 비교할만한 행성들끼리 짝을 지어서 거리를 구함으로써 시간복잡도를 줄일 수 있고 '비교할만한'이라는 기준을 세움으로써 짝을 지을 수 있다.

 

터널을 연결하는 비용은 두 행성의 좌표들 중 차이가 가장 적은 것의 절대값이다.

그 말은 즉, 실제 좌표계처럼 세 점의 차이를 제곱하고 루트를 씌우는 것이 아니라 그저 좌표의 차이가 가장 적은 것만 찾으면 된다는 것이다.

 

여기서 힌트를 얻을 수 있다.

행성끼리의 간선을 구할 때 가장 가까운 것들끼리 간선을 구할 것이고 가장 가까운 것들은 세 좌표 중 한 좌표를 기준으로 정렬했을 때 앞,뒤에 위치할 것이다.

x,y,z를 기준으로 정렬했을 때, 인접한 행성들끼리 비용을 구해서 간선을 정하면 되는 것이다.

그렇게 구한 모든 간선들을 하나의 배열edge에 넣고 크루스칼 알고리즘을 수행하면 최소 스패닝 트리가 완성된다.