행성 터널

• 최소 신장 트리 (Minimum Spanning Tree / MST)의 응용.
• 완전 그래프를 그려서 O(n^2)개의 엣지를 모두 고려해서 풀려고 한다면, 프림 알고리즘을 써도 O(n^2)이 걸린다. 하지만 이 문제에서는 고려해야할 엣지 갯수를 효율적으로 줄일 수 있다.
• 그냥 x좌표만 갖고 있는 1차원 상의 점들이라고 생각해보면, 인접한 점들간의 엣지들만 연결해주면 최소 코스트로 전체를 연결할수 있다는 것을 쉽게 알수 있다. x_i < x_j < x_k 이라면 (i,k)엣지를 연결하는 것보다 (i,j)와 (j,k)를 연결하는 것이 같은 비용으로 더 많은 노드를 연결할수 있으므로, 인접하지 않은 점들 사이의 엣지는 필요가 없다.
• 그래서, x축, y축, z축 기준으로 각각 점들을 정렬하고, 인접한 점들 사이의 엣지들만 남기면 엣지의 수는 O(n)개가 된다. 이제 이 엣지들을 가지고 MST를 구하면 O(nlogn)의 시간복잡도로 계산이 가능하다.

"""Solution code for "BOJ 2887. 행성 터널".

- Problem link: https://www.acmicpc.net/problem/2887
- Solution link: http://www.teferi.net/ps/problems/boj/2887

Tags: [Minimum spanning tree]
"""

import itertools
import sys
from teflib import graph as tgraph


def main():
    N = int(sys.stdin.readline())
    coords = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
    edges = []
    for k in range(3):
        # pylint: disable=cell-var-from-loop
        sorted_planets = sorted(range(N), key=lambda i: coords[i][k])
        for u, v in itertools.pairwise(sorted_planets):
            edges.append((u, v, coords[v][k] - coords[u][k]))

    mst_edges = tgraph.minimum_spanning_tree(edges, N)
    print(sum(w for u, v, w in mst_edges))


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.minimum_spanning_tree