별자리 만들기

• 2차원에서의 유클리디안 최소 신장 트리 (Minimum Spanning Tree / MST) 문제.
• 유클리디안 MST는 링크에 설명했듯이 (구현은 안해봤지만) O(nlogn)에 풀수 있는 효율적인 알고리즘도 있지만, n이 워낙 작아서 그냥 일반적인 MST 알고리즘을 써도 충분히 빠르다. 심지어는, 이 문제에서는 O(n^2)의 프림 알고리즘보다, O(n^2logn)의 크루스칼 알고리즘이 실제로는 살짝 더 빠르게 돌았다.

"""Solution code for "BOJ 4386. 별자리 만들기".

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

Tags: [MST]
"""

import math
from teflib import graph as tgraph


def main():
    n = int(input())
    coords = [[float(x) for x in input().split()] for _ in range(n)]

    mat_graph = tgraph.create_mat_graph(
        n, lambda u, v: math.dist(coords[u], coords[v]))
    mst_edges = tgraph.minimum_spanning_tree_dense(mat_graph)
    answer = sum(w for u, v, w in mst_edges)
    print(f'{answer:.2f}')


if __name__ == '__main__':
    main()

• Dependency
  • teflib.graph.minimum_spanning_tree_dense
  • teflib.graph.create_mat_graph

"""Solution code for "BOJ 4386. 별자리 만들기".

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

Tags: [Minimum spanning tree]
"""

import math
import sys
from teflib import graph as tgraph


def main():
    n = int(input())
    coords = []
    edges = []
    for u in range(n):
        coord_u = [float(x) for x in sys.stdin.readline().split()]
        edges.extend((u, v, math.dist(coord_u, coord_v))
                     for v, coord_v in enumerate(coords))
        coords.append(coord_u)

    mst_edges = tgraph.minimum_spanning_tree(edges, n)
    answer = sum(w for u, v, w in mst_edges)
    print(f'{answer:.2f}')


if __name__ == '__main__':
    main()