크루스칼 알고리즘

문제 출저 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 풀이 별들의 좌표가 주어진다. 별들의 거리는 직각 삼각형 공식으로 구할 수 있다. 이 때, 모든 별들을 연결했을 때 가장 적은 거리가 무엇인지 구해야한다. 이 문제는 최소 스패닝 트리로 크루스칼 알고리즘으로 풀었다. 먼저 PriorityQueue pq를 선언하였다. 이 PriorityQueue는 두 별의 거리를 저장하는 용으로 거리를 오름차순으로 정렬했다. dot에는 int s, i..

목차 개념 크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됩니다. 그래프에는 정점과 간선이 있는데, 간선에 가중치가 포함되어 있습니다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용합니다. 즉, 최소 신장 트리를 구하기 위한 알고리즘 입니다. 신장 트리와 최소 신장 트리 신장 트리(Spannging tree) 다음과 같이 정의합니다. 그래프에서 1) 모든 정점을 포함하고 2) 정점 간 서로 연결되어 있으며 싸이클이 존재하지 않는 그래프 (싸이클이 존재하는 않는 것은 tree 기본 조건) 예를 들어 아래와 같은 그래프가 있다고 가정해 보겠습니다. 여기서 나올 수 있는 신장..