[Python] 백준 2887 - 행성터널

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

2887번: 행성 터널

 

크루스칼 문제다.

일반적인 크루스칼 개념을 적용시켜서 푸는 것은 동일하다.

각 노드의 x축 y축 z축 차이를 탐색한 뒤에 절댓값이 가장 작은 가중치를 선택하면 된다.

그렇다고 모든 노드를 하나씩 비교해보면 시간초과가 난다.

 

따라서 간선의 가중치와 노드를 저장한 뒤에 우선순위 정렬을 시행한 뒤 비교해줘야한다.

 

정리해보면

1. x축 y축 z축의 리스트를 하나 만든다.

2. 각  리스트에 x축, y축, z축 값을 노드번호와 함께 저장한다.

3. 각 리스트를 가중치 우선순위로 정렬시킨다.

4. 앞에서부터 2개씩 순차적으로 비교하며 해당 간선과 노드를  edges 리스트에 저장한다.

5. edges를 정렬시킨다.

6. 크루스칼 알고리즘을 진행한다.

def find_parent(parent, x):
    if parent[x] !=x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
    
n = int(input())

xs, ys, zs = [], [], []
# 간선의 가중치와 노드를 저장 후 정렬
for i in range(1,n+1):
    x,y,z = map(int,input().split())
    xs.append((x,i))
    ys.append((y,i))
    zs.append((z,i))
xs.sort()
ys.sort()
zs.sort()

parent = [i for i in range(n+1)]
result = 0

edges = []
# cost: xs[i][0]
# location: xs[i][1]
for i in range(n-1):
    edges.append((xs[i+1][0] - xs[i][0], xs[i][1],xs[i+1][1]))
    edges.append((ys[i+1][0] - ys[i][0], ys[i][1],ys[i+1][1]))
    edges.append((zs[i+1][0] - zs[i][0], zs[i][1],zs[i+1][1]))
edges.sort()

for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result+=cost
print(result)