코딩테스트 준비(kotlin)/그래프2 [kotlin] 별자리 만들기 별자리 만들기 문제 및 입출력 풀이 접근 별자리를 잇는다? -> 그래프 형식으로 나오겠구나 ?선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용 -> 최소신장트리(MST)를 구축하면 되겠구나? 풀이 코드 package com.chanhue.algorithm.백준.골드import java.util.PriorityQueueimport kotlin.math.sqrtfun main() { val n = readLine()!!.toInt() val node = mutableListOf>() repeat(n) { val (x, y) = readLine()!!.split(" ").map { it.toDouble() } node... 2025. 4. 12. [kotlin, 프로그래머스] 최소신장트리 문제와 입출력최소 신장 트리 (Minimum Spanning Tree, MST)의 정의와 특징정의최소 신장 트리는 가중치가 할당된 무방향 그래프에서 모든 정점을 포함하면서 간선의 가중치 합이 최소가 되는 트리입니다.특징트리의 간선 수: (V - 1)개의 간선을 가집니다.사이클 없음: 트리 구조이므로 사이클을 형성하지 않습니다.가중치 최소화: 모든 정점을 연결하면서 간선의 가중치 합이 최소가 되어야 합니다.사용 예통신 네트워크 구축: 노드들을 가장 적은 비용으로 연결할 때 사용됩니다.최소신장트리(MST) 구현 방법 - 크루스칼 알고리즘, 프림 알고리즘 사용 크루스칼간선을 가중치 순으로 정렬 후, 작은 것부터 선택 (사이클 방지)간선 정렬 + 유니온 파인드 (Union-Find)프림정점 기준으로, 현재 트리.. 2025. 4. 12. 이전 1 다음
