광활한 우주에서 행성 간 터널을 만들 때 비용이 세 좌표 축 상 거리 중 가장 짧은 것으로 할 때, 모든 행성이 서로 연결되게 하는 경우의 최소 비용을 구하는 문제입니다. 보아하니 MST를 사용하여 푸는 문제인 것 같은데, 여느 문제처럼 완전 그래프를 만든 후 MST를 구성하려고 보니 N값이 너무 큽니다(≤100000). 메모리가 터질 것이 분명하기 때문에 다른 방법을 생각해야합니다. 그런데 문제에서 주어진 비용을 보면 조금 특이합니다. 왠지 각 좌표 별(x, y, z)로 정렬한 후 인접한 행성끼리만 터널을 생성하고 MST를 구성하면 될 것 같기도 합니다. 그리고 실제로 됩니다!! ??? 사실 왜 되는지는 모르겠지만 되지 않을까 싶어서 했는데 진짜 돼서 놀랐습니다…
PS알못 OrbitHv의 PS