백준 2887
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
시행착오 1
행성 사이의 터널 개수 설정을 nC2로 설정하고 쿠르스칼 알고리즘을 쓰니
메모리 초과가 났다. n의 수가 생각보다 커서 n^2의 크기를 담는 리스트에서 초과가 난 모양이었다.
시행착오 2
해서 x축 y축 z축의 좌표를 따로 받아서 정렬한 다음 터널의 비용과 노드의 위치를 나타내는 edges 리스트에 추가하는 코드를 작성하였다.
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())
planetx = []
planet_y = []
planet_z = []
edges = []
result = 0
parent = [[] for in range(n)]
for i in range(n):
parent[i] = i
for i in range(n):
x, y, z =list(map(int, input().split()))
planet_x.append(x)
planet_y.append(y)
planet_z.append(z)
planet_x.sort()
planet_y.sort()
planet_z.sort()
print(planet_x)
print(planet_y)
print(planet_z)
for i in range(n - 1):
edges.append((planet_x[i + 1] - planet_x[i], i, i + 1))
edges.append((planet_y[i + 1] - planet_y[i], i, i + 1))
edges.append((planet_z[i + 1] - planet_z[i], i, 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)
result += cost
print(result)
여기서 문제점은 planet_x, planet_y, planet_z 리스트에 추가할 때 인덱스 값을 같이 튜플로 저장해 주지 않고 edges에 추가할 때 그냥 i값을 index로 생각하고 넣어주어 정렬을 하는 과정 중에 노드의 번호가 엇갈려 제출 했을 때 틀리게 나왔다.
결론
planet_x, planet_y, planet_z에 append할 때 해당 index값을 같이 튜플로 저장해서 정렬해도 노드 번호도 같이 이동하여 올바른 답을 도출해낼 수 있었다.
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())
planet_x = []
planet_y = []
planet_z = []
edges = []
result = 0
parent = [[] for _ in range(n)]
for i in range(n):
parent[i] = i
for i in range(n):
x, y, z =list(map(int, input().split()))
planet_x.append((x, i))
planet_y.append((y, i))
planet_z.append((z, i))
planet_x.sort()
planet_y.sort()
planet_z.sort()
print(planet_x)
print(planet_y)
print(planet_z)
for i in range(n - 1):
edges.append((planet_x[i + 1][0] - planet_x[i][0], planet_x[i][1], planet_x[i + 1][1]))
edges.append((planet_y[i + 1][0] - planet_y[i][0], planet_y[i][1], planet_y[i + 1][1]))
edges.append((planet_z[i + 1][0] - planet_z[i][0], planet_z[i][1], planet_z[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)
