[python] 백준 2887 행성 터널

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

2887번: 행성 터널

 

 

문제 해결

• 최소 거리를 측정해야하는데 각 축에서 가장 차이가 작은 값으로 거리를 정의한다.
• 축을 분리해서 정렬 후 (오름차순) 거리차를 계산하는 것은 짐작할 수 있다.
• 그 후 점을 연결시키는데 이미 연결 되어있으면 넘어가고 아니면 점을 연결하고 비용을 추가해준다.
• 연결 되어있고 아니고를 유니온-파인드(Union-find)를 통해 계산한다.
• 이와 같은 방법을 크루스칼-알고리즘(Kruskal-algorithm)이라 한다.

아래를 참고하였다.

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)

CODE

# 2887
import sys
input = sys.stdin.readline

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


def union_parent(parents,a,b):
    a = find_parent(parents,a)
    b = find_parent(parents,b)
    if a<b:
        parents[b] = a
    else:
        parents[a] = b

def kruskal():
    result_cost = 0
    for cost, a, b in edges:
        if find_parent(parents,a) != find_parent(parents,b):
            union_parent(parents, a, b)
            result_cost += cost
    print(result_cost)

if __name__ == "__main__":
    N = int(input())
    P_x = []
    P_y = []
    P_z = []
    for i in range(N):
        x, y, z = map(int, input().split())
        P_x.append((x,i))
        P_y.append((y,i))
        P_z.append((z,i))
    
    P_x.sort()
    P_y.sort()
    P_z.sort()

    edges = []
    for curList in P_x, P_y, P_z: # P_x, P_y, P_z 순서
        for i in range(1,N):
            w1, a = curList[i-1]
            w2, b = curList[i]
            edges.append((abs(w1-w2), a, b))
    edges.sort()
    parents = [i for i in range(N)]
    kruskal()