[파이썬] 백준 2887번 행성 터널

백준 #2887 행성 터널

• 백준 2887번 행성 터널 문제풀기

# N개의 행성
# 터널 연결비용 min(|xa - xb|, |ya - yb|, |za - zb|)
# 터널 N-1개

# 출력: 모든 행성을 터널로 연결하는데 필요한 최소 비용

# 체크할 조건
# N <= 100000
    # 간선을 있는 대로 다 만들면 시간초과

# 크루스칼 알고리즘
# x, y, z 모두 각각 정렬한 후 
# 10만개의 좌표에 대해서 인접한 점만 검사해서 edge에 넣는다.

import sys
input = sys.stdin.readline

def find(x, parents):
    if parents[x] == x: return x
    parents[x] = find(parents[x], parents)
    return parents[x]

def union(x, y, parents, ranks):
    xr = find(x, parents)
    yr = find(y, parents)
    if ranks[xr] >= ranks[yr]:
        parents[yr] = xr
    else:
        parents[xr] = yr
    if ranks[xr] == ranks[yr]:
        ranks[xr] += 1

def kruskal(edges, parents, ranks, cnt):
    cost = 0
    for val, x, y in edges:
        if not cnt: return cost
        if find(x, parents) != find(y, parents):
            union(x, y, parents, ranks)
            cnt -= 1
            cost += val
    return cost

def solution(N):
    parents = [i for i in range(N)]
    ranks = [0 for i in range(N)]
    planets = []
    edges = []

    for i in range(N):
        x, y, z = map(int, input().split())
        planets.append([x, y, z, i])
    
    cnt = N-1
    for i in range(3):
        planets.sort(key=lambda x: x[i])
        for j in range(1, N):
            nowv, nowi = planets[j][i], planets[j][3]
            prevv, previ = planets[j-1][i], planets[j-1][3]
            edges.append([abs(nowv - prevv), nowi, previ])
    
    edges.sort()
    print(kruskal(edges, parents, ranks, cnt))

if __name__ == '__main__':
    solution(int(input()))