백준(2887) - 행성터널 Python

백준(2887) - 행성터널

문제풀이 : 그래프, 파이썬

해결방법

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

크루스칼 알고리즘을 확인할때, 최소 비용부터 union 하며 결과를 확인해야한다.

1. 먼저 x, y ,z 좌표를 각각 따로 입력 받고 정렬한다.

2. 그 후 x,y,z의 비용차이를 행성의 번호와 같이 리스트에 입력받고, 비용을 오름차순으로 정렬한다.

3. 최소신장 트리를 만들 때까지 union 한 후 최소비용을 출력한다.

import sys
input = sys.stdin.readline

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 = [i for i in range(n + 1)]

x_list = []
y_list = []
z_list = []
for i in range(1, n + 1):
    x, y, z = map(int,input().split())
    x_list.append((x, i))
    y_list.append((y, i))
    z_list.append((z, i))

x_list.sort()
y_list.sort()
z_list.sort()

count_list = []
for i in range(1, n):
    count_list.append((abs(x_list[i][0] - x_list[i-1][0]), x_list[i][1], x_list[i-1][1]))
    count_list.append((abs(y_list[i][0] - y_list[i-1][0]), y_list[i][1], y_list[i-1][1]))
    count_list.append((abs(z_list[i][0] - z_list[i-1][0]), z_list[i][1], z_list[i-1][1]))
count_list.sort()

res = 0
answer = 0
for co in count_list:
    cost, a, b = co
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        answer += cost
        res += 1
    if res == n:
        break

print(answer)