[알고리즘][Python] 백준 2887 행성터널 문제 풀이

문제 출처 : www.acmicpc.net/problem/2887

2887번: 행성 터널

---

문제 해석 : 행성 터널을 건설하는데 N개 행성에 대해서 N-1개의 터널을 최소 비용으로 구하는 문제이다.

 

문제 풀이 :  모든 경로를 생성하고 문제를 풀이하고자 한다면 메모리 초과 또는 시간 복잡도에서 초과가 날 것이다. 따라서 x,y,z에 대해서 정렬을 실행하고 각각 사이의 거리를 저장한 다음 이를 간선으로 취급해서 MST를 실행하면 된다.

-> 중복 되는 경우를 제외하기 위해서 임의의 행성번호를 추가하여 한 행성에 대해서 1개의 최소간선이 되도록 한다.

---

풀이 코드

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())

parent = [0] * (N + 1)

result = 0
route = []

for i in range(1, N + 1):
    parent[i] = i

arr1 = []
arr2 = []
arr3 = []

for i in range(1, N+1):
    x, y, z = map(int, input().split())
    arr1.append((x,i))
    arr2.append((y,i))
    arr3.append((z,i))

arr1.sort()
arr2.sort()
arr3.sort()

for i in range(N-1):
    route.append((abs(arr1[i+1][0] - arr1[i][0]), arr1[i][1], arr1[i+1][1]))
    route.append((abs(arr2[i+1][0] - arr2[i][0]), arr2[i][1], arr2[i+1][1]))
    route.append((abs(arr3[i+1][0] - arr3[i][0]), arr3[i][1], arr3[i+1][1]))

route.sort()

for edge in route:
    cost, x, y = edge

    if find_parent(parent, x) != find_parent(parent, y):
        union_parent(parent, x, y)
        result += cost

print(result)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.