문제 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 프림 알고리즘을 사용하였다. 문제는 각 정점의 위치가 주어지기 때문에, 정점들 간의 거리를 계산하여 간선의 정보를 우선 순위 큐 리스트에 저장해준다. 그리고 나서 프림 알고리즘을 이용하여 최소 스패닝 트리를 구하고 결과를 출력해준다. 코드 import java.util.* import kotlin.math.* // 별의 좌표 정보를 저장하는 데이터 클래..

문제 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제로 프림과 크루스칼 알고리즘을 이용해 풀이할 수 있다. 이번 문제에서는 프림 알고리즘을 사용하였다. 프림 알고리즘의 주요 단계는 다음과 같다. 1. 노드 선택: 임의의 노드를 선택하여 시작한다. 2. 우선 순위 큐 생성: 선택한 노드와 연결된 모든 간선을 우선 순위 큐에 추가한다. 이때, 간선의 가중치를 기준으로 오름 차순 정렬된다. 3. 최소 간선 선택: 우선 순위 큐에서 ..