[크루스칼] 백준 2887번 '행성 터널' (Python)

<문제 링크>

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

2887번: 행성 터널

---

<문제 풀이>

1. 모든 행성이 연결되도록 요구하므로, 최소 신장 트리를 만드는 문제임

2. x,y,z축 정렬 후 n-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 = [i for i in range(n + 1)]

edges = []
result = 0

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

for i in range(n-1):
    edges.append((x_list[i+1][0] - x_list[i][0], x_list[i][1], x_list[i+1][1]))
    edges.append((y_list[i+1][0] - y_list[i][0], y_list[i][1], y_list[i+1][1]))
    edges.append((z_list[i+1][0] - z_list[i][0], z_list[i][1], z_list[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)

 

<고쳐야 할 점>

• 문제 푸는 방법 이해하기
• 크루스칼 알고리즘 외우기
• 복습 알고리즘