[🥇1 / 백준 2887 / 파이썬] 행성 터널

 

2887번: 행성 터널

 

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(x_A, y_A, z_A)와 B(x_B, y_B, z_B)를 터널로 연결할 때 드는 비용은 min(|x_A-x_B|, |y_A-y_B|, |z_A-z_B|)이다.

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

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -10⁹보다 크거나 같고, 10⁹보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

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

 

예제 입력  5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19

예제 출력  4

 

풀이

 

간선이 주어지지 않는 문제이므로 직접 간선을 만들어야 한다.

한 행성에서 다른 행성과의 모든 간선을 만들어보기엔 100,000 * 100,000 * 3, 즉 O(N^2) 정도의 연산이 소모되므로 스패닝 트리를 구성하기도 전에 시간초과가 날 것이다.

따라서 모든 간선을 만들어보지 않고, 선택될 가능성이 있는 간선만 구성해야 한다.

필자는 크루스칼로 해결했기 때문에, 따로 인접 리스트를 만들거나 하진 않을 것이다.

 

어떠한 간선이 선택받을 가능성이 있을까? 단연 x, y, z 상관없이 비용이 가장 작은 간선이 선택될 것이다.

그리고 비용은 절대값이기 때문에 가장 근거리에 있는 행성들을 고르는 것이 제일 비용이 적다.

그렇다면 x, y, z 기준으로 각각 정렬한 뒤 인접한 행성들의 비용을 구해 간선을 구성하면 될 것이다.

또한 정렬할 때 정점을 알아야 하므로 행성 번호를 주어 구분하도록 했다.

 

예제를 예로 든다면 간선 리스트는 다음과 같이 구성된다. (가중치, 행성a, 행성b)

 

(20, 3, 4), (11, 2, 3), (10, 1, 2), (10, 0, 1), (5, 1, 4), (4, 2, 3), (3, 4, 2), (3, 0, 1), (1, 3, 0), (1, 1, 3), (0, 3, 4), (0, 0, 1)

 

작은 것부터 pop을 할 것이므로 내림차순으로 정렬했다.

 

 

이제 가중치가 가장 작은 간선부터 차례대로 뽑아, 크루스칼 알고리즘을 진행한다.

크루스칼은 가중치가 가장 작은 간선부터 n-1 개를 뽑아 스패닝 트리를 구성하는 알고리즘이다. (n = 정점의 개수)

 

다만 크루스칼에서는 유니온 파인드를 통해 간선이 사이클을 이루는지 검사해야 한다.

만약 사이클을 이룬다면 현재 선택된 간선이 아무리 가중치가 적더라도 최소 스패닝 트리를 구성할 수 없으므로 버리고, 다음 간선을 다시 선택한다.

사이클만 검사하는 과정에서 중복된 간선도 걸러지기 때문에, 중복된 간선 선택에 대해서는 염려하지 않아도 된다.

 

이렇게 총 n-1개의 간선이 선택된다면 성공적으로 최소 스패닝 트리를 구성한 것이다.

 

import sys
input = sys.stdin.readline

def union(x,y):
    x = find(x)
    y = find(y)
    parents[y] = x

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

# 좌표를 x,y,z 별로 저장하고 정렬
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 curList in xlst,ylst,zlst:
    for i in range(1,n):
        w1,a = curList[i-1]
        w2,b = curList[i]
        edges.append((abs(w1-w2),a,b))
edges.sort(reverse = True)

# 크루스칼 진행
parents = [i for i in range(n+1)]
cnt,ans = n-1,0
while cnt:
    w,a,b = edges.pop()
    if find(a) == find(b):
        continue
    union(a,b)
    cnt-=1
    ans+=w
print(ans)