[크루스칼] 행성터널

[ericagong]

⭐ 성찰

1. 크루스칼 O(ElogE)에서 시간 복잡도가 초과하는 경우, 전체 고려해야하는 간선 수 E를 어떻게 줄일 수 있을지 고민해야함.

❓ 문제 상황

행성터널

👨‍💻 문제 해결: 최소 신장 트리

⏳ 시간복잡도

• N = 행성 수 = 200,000
• E = 행성 간 간선 수 = N(N-1) = 400,000,000,000
• 따라서 크루스칼 O(ElogE)로 풀이할 경우, 주어진 시간안에 풀이 불가
• 모든 간선의 수에 대해 고려하지 않고, ⭐ 선택 가능한 간선에 대해서만 고려하도록 해 E의 크기를 줄여야함. ⭐
• 문제에서 행성 간의 비용은 min(|X1-X2|, |Y1-Y2|, |Z1-Z2|)라 하였으므로, 모든 X값, Y겂, Z값을 각각 별도의 리스트에 넣어줌.
• X축에 대해 정렬을 수행하면, X축 상에 인접한 Xi 와 Xi+1이 X축 상의 행성 i, i+1 비용의 최소값이 되기 때문에 X축 상의 다른 간선은 고려할 필요가 없음.
• 즉, 각 축 별로 (N-1)개의 간선이 나오며, min(|X1-X2|, |Y1-Y2|, |Z1-Z2|)이라 하였으므로, X축, Y축, Z축 총 3(N-1)개의 간선들만 고려해주면 E의 수를 3 * (200,000-1) 로 줄여 주어진 시간 안에 풀이 가능함.

✅ 1차 풀이: 크루스칼

1. x, y, z 축 별로 별동의 리스트에 저장한 뒤 정렬 수행. 정렬을 위해 반드시 (비용, 노드 번호) 순으로 입력.
2. x, y, z 축의 인접한 두 노드 사이의 비용을 계산하여 edges에 추가
3. edges를 정렬
4. 크루스칼 진행

   
   import sys

input = sys.stdin.readline n = int(input()) edges = [] result = 0 parents = [0] * (n+1)

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

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

for i in range(1, n+1): parents[i] = i

x, y, z 축 별로 저장

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

x, y, z 축 별로 정렬

xs.sort() ys.sort() zs.sort()

x, y, z 축 별로 인접한 두 지점 사이의 간선만 edges에 추가

for i in range(n-1): edges.append((abs(xs[i+1][0] - xs[i][0]), xs[i][1], xs[i+1][1])) edges.append((abs(ys[i+1][0] - ys[i][0]), ys[i][1], ys[i+1][1])) edges.append((abs(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(parents, a) != find_parent(parents, b): union_parent(parents, a, b) result += cost

print(result)