문제
- N개의 행성에 N-1개의 터널을 만들어 서로 연결되게 할 때, 필요한 최소 비용은?
- 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)
풀이
- $O(N^2)$ 이 아닌 풀이가 생각나지 않아 한참 고민한 문제.
- 크루스칼로 $O(NlogN)$ 안에 해결 가능하다.
- 포인트는 x, y, z 축으로 각각 정렬한 후 N-1 개의 간선만 고려해서 최소 신장 트리를 만든다는 것
- 정렬하고 난 뒤 바로 옆 간선이 아니면 더 큰 비용이 되니까..
- sys.stdin.readline 사용해야 시간초과 안걸린다.
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())
x = [] # x 좌표
y = [] # y 좌표
z = [] # z 좌표
for i in range(1, N+1):
coor = list(map(int, input().split()))
x.append((coor[0], i))
y.append((coor[1], i))
z.append((coor[2], i))
x.sort()
y.sort()
z.sort()
parent = [i for i in range(N+1)] # 부모 테이블
edges = [] # 간선 리스트
answer = 0 # 터널 연결 비용
# 각 좌표별 N-1 개의 간선 추가
for i in range(N-1):
edges.append((x[i+1][0] - x[i][0], x[i+1][1], x[i][1]))
edges.append((y[i+1][0] - y[i][0], y[i+1][1], y[i][1]))
edges.append((z[i+1][0] - z[i][0], z[i+1][1], z[i][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)
answer += cost
print(answer)
References