사용자 도구

사이트 도구


ps:problems:boj:4386

별자리 만들기

ps
링크acmicpc.net/…
출처BOJ
문제 번호4386
문제명별자리 만들기
레벨골드 4
분류

최소 신장 트리

시간복잡도O(n^2logn)
인풋사이즈n<=100
사용한 언어Python
제출기록32952KB / 76ms
최고기록56ms
해결날짜2022/10/04
태그

30단계 [라이]최소 스패닝 트리

풀이

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

코드

코드 1 - Prim

"""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()

코드 2 - Krusakal

"""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()

토론

댓글을 입력하세요:
Q R T Q F
 
ps/problems/boj/4386.txt · 마지막으로 수정됨: 2022/10/18 08:21 저자 teferi