우주 정거장 건설
면접 대비시간 제한2초메모리 제한512 MB
3차원 공간의 구 n개가 주어질 때, 서로 닿거나 겹치는 구는 이미 연결된 것으로 보고 모든 구를 잇는 최소 총 복도 길이를 구한다.
문제
당신은 우주 정거장 엔지니어링 팀의 일원으로, 정거장 건설 과정에서 맡은 작업이 하나 있다. 이 작업을 수행하는 컴퓨터 프로그램을 작성해야 한다.
우주 정거장은 셀이라 불리는 여러 단위로 이루어져 있다. 모든 셀은 구 모양이지만, 크기가 반드시 균일하지는 않다. 각 셀은 정거장이 궤도에 성공적으로 올라간 직후 미리 정해진 위치에 고정된다. 두 셀이 서로 닿아 있거나 심지어 겹쳐 있을 수도 있다는 점이 상당히 이상하다. 극단적인 경우에는 한 셀이 다른 셀을 완전히 감쌀 수도 있다. 이런 배치가 어떻게 가능한지는 나도 모르겠다.
승무원이 어떤 셀에서 다른 셀로도 걸어갈 수 있어야 하므로, 모든 셀은 연결되어 있어야 한다. 셀 A에서 다른 셀 B로 걸어갈 수 있는 경우는 (1) A와 B가 서로 닿아 있거나 겹쳐 있을 때, (2) A와 B가 '복도'로 연결되어 있을 때, (3) A에서 C로, B에서 C로 각각 걸어갈 수 있는 셀 C가 존재할 때이다. 조건 (3)은 추이적으로 해석해야 한다.
당신은 어떤 셀 쌍을 복도로 연결할지, 즉 배치를 설계해야 한다. 복도 배치에는 어느 정도 자유도가 있다. 예를 들어 서로 닿지도 겹치지도 않는 세 셀 A, B, C가 있을 때, 세 셀을 모두 연결하는 방법은 적어도 세 가지가 가능하다. 첫째는 복도 A-B와 A-C를 짓는 것, 둘째는 B-C와 B-A를 짓는 것, 셋째는 C-A와 C-B를 짓는 것이다. 복도 건설 비용은 길이에 비례하므로, 복도 총 길이가 가장 짧은 계획을 선택해야 한다.
복도의 폭은 무시해도 된다. 복도는 두 셀 표면 위의 점 사이에 짓는다. 복도는 얼마든지 길게 지을 수 있지만, 당연히 가장 짧은 것을 고른다. 두 복도 A-B와 C-D가 공간에서 교차하더라도, 예를 들어 A와 C 사이의 연결 경로를 이루는 것으로 간주하지 않는다. 다시 말해 두 복도는 절대 교차하지 않는다고 생각해도 된다.
입력
입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.
n
x1 y1 z1 r1
x2 y2 z2 r2
...
xn yn zn rn
데이터 세트의 첫 줄에는 셀의 개수인 정수 n이 들어 있다. n은 양수이며 100을 넘지 않는다.
다음 n개 줄은 셀의 설명이다. 한 줄에 있는 네 값은 구의 중심의 x, y, z 좌표와 반지름(이 문제의 나머지 부분에서 r이라 부른다)을 이 순서대로 나타낸다. 각 값은 소수점 아래 3자리까지 있는 소수로 주어지며, 값은 공백 문자로 구분된다.
x, y, z, r은 각각 양수이고 100.0보다 작다.
입력의 끝은 0만 들어 있는 줄로 나타낸다.
출력
각 데이터 세트마다 복도의 최소 총 길이를 한 줄에 하나씩 출력한다. 출력하는 값은 소수점 아래 3자리까지 있어야 하며, 오차가 0.001을 넘어서는 안 된다.
복도가 필요 없는 경우, 즉 모든 셀이 복도 없이 연결되어 있으면 복도의 최소 총 길이는 0.000이다.