(Python/플5)백준알고리즘 2887번: 행성 터널

 

문제 바로가기 

 

행성 터널

문제:

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력:

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

 

출력:

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

 

풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(input())

# 거리가 가까운 순서대로 행성을 이루어줌 .
X, Y, Z = [], [], []
for i in range(N):
    x, y, z = map(int, sys.stdin.readline().rstrip().split(" "))
    X.append((x, i))
    Y.append((y, i))
    Z.append((z, i))

# x, y, z 좌표를 기준으로 정렬
X.sort()
Y.sort()
Z.sort()

graph = []
for i in range(1, N):
    # x, y, z 좌표를 기준으로 정렬한 리스트에서 각 행성들 간의 간선 비용 계산
    x_cost = abs(X[i][0] - X[i-1][0])
    y_cost = abs(Y[i][0] - Y[i-1][0])
    z_cost = abs(Z[i][0] - Z[i-1][0])

    # (간선 비용, 행성 A 번호, 행성 B 번호) 형태의 튜플을 graph 리스트에 추가
    graph.append((x_cost, X[i][1], X[i-1][1]))
    graph.append((y_cost, Y[i][1], Y[i-1][1]))
    graph.append((z_cost, Z[i][1], Z[i-1][1]))

graph.sort()  # 간선 비용 기준으로 정렬 최솟값 기준으로 해야하므로 reverse 해줌
graph.sort(key =lambda x:-x[0])

parents = [i for i in range(N+1)]
def find(node):
    if node != parents[node]:
        parents[node] = find(parents[node])
    return parents[node]
def union(node1,node2):
    if node1 > node2:
        parents[node1] = node2
    else:
        parents[node2] = node1

res = 0
count = 0
while graph:
    s,e,w = graph.pop()
    if count == N:
        break
    node1 = find(e)
    node2 = find(w)
    if node1 != node2:
        union(node1,node2)
        count += 1
        res += s
print(res)

 

이 문제는 크루스칼 알고리즘을 사용해서 풀었다. 

 

다만 간선이 연결되어있는것이 정확히 나와있지않아서 거리가 가장 가까운 행성들의 거리를 각 리스트에 넣어주고 행성번호도 넣어준다.

 

거리가 가까운 행성들로 부터 간선비용으로 정렬을하고 reverse 해준다.

 

graph 에서 1개 씩 뽑아 최솟값 기준으로 뽑아줘야하기때문이다.