https://www.acmicpc.net/problem/4386 ✨ 자바로 푸는 별자리 만들기 문제 풀이 📌 문제 개요 백준 4386번 “별자리 만들기”는주어진 N개의 별 좌표를 기반으로 별자리를 만들 때,모든 별을 연결하면서 최소한의 선분 길이 합을 구하는 문제입니다. 즉, 모든 별을 잇되 최소 비용으로 연결하는 구조를 요구하며, 이는 전형적인 최소 신장 트리(MST, Minimum Spanning Tree) 문제입니다. 💡 예제 입력31.0 1.02.0 2.02.0 4.0 예제 출력3.41 🛠 알고리즘 접근 방식 별들 간 거리를 간선으로 보고,이 중에서 가장 적은 거리의 간선들만을 선택해 모든 별을 연결해야 합니다. 이를 위해 프림 알고리즘을 사용합니다.(크루스칼도 가능하지만, 이 코..

https://www.acmicpc.net/problem/1197   크루스칼 알고리즘을 활용하여 문제를 풀이하였다.최근 문제 풀이한 것 중에서 크루스칼이 있었고 간선을 가중치기준으로 정렬하여풀었던 기억이 있어 그방식대로 풀었다. 풀이과정은 비교적 간단하고이번 문제 풀이에서 기억에 남는것은  union find 를 활용할 때경로 압축이다. find() 함수에서 if(p[a] == a) 일때 return a를 하는것이아니라if(p[a]!=a) 일때 p[a] = find(a)를 해주고 return p[a] 를 하게되면 정점의갯수가 많아지고 간선이 많아지더라도 시간복잡도가 확실히 줄어든 다는점을알게되었다. 예를들어 정점이 6개고 parent 배열이 union(1, 2), union(2, 3) union(3, ..