백준 4386 python1 4386. 별자리 만들기 (Python) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 모든 별들이 사이클이 없는 그래프로 연결되어 있으면 된다. 즉, N개의 별이 있을 때 N-1개의 간선을 사용하여 연결하는 최소 스패닝 트리를 구하면 된다. 최소 스패닝 트리를 만들기 위해서 사용되는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 일반적으로 크루스칼 알고리즘은 정점에 비해 간선의 개수가 적을 때 사용하면 좋고 프림 알고리즘은 정점에 비해 간선의 개수가 많을 때 사용하면 좋다. 해당 문제는 모든 별들끼리의 길이를 구한 후 최소 스패닝 트.. 2022. 6. 27. 이전 1 다음
