크루스칼

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 크루스칼 (유니온파인드) 1. 유니온 파인드 배열을 초기화한다. 2. 그래프 데이터를 가중치 기준으로 오름차순 정렬한다. // == Arrays.sort(costs, (o1,o2) -> Integer.compare(o1[2], o2[2])); Arrays.sort(costs, new Comparator() { @Override public int compare(int[] o1, int[] o2) { // 값이 작은 순 정렬 return o1[2] - o2[2]; } }); 3. 가중..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 import java.util.*; import java.io.*; public class Main { static in..

📍 정의 및 특징 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리 - 사이클 X - 에지 중심! - 노드가 N개일 때, MST를 구성하는 에지 개수는 항상 N-1개 - 대표 : 크루스칼(그리디), 프림 알고리즘 #사이클X #에지 #가중치합 #크루스칼 #프림 📍 필요 변수 1. 에지 클래스 - 노드 변수 2개 - 가중치 변수 2. 그래프 에지 리스트 - PriorityQueue edges 3. 유니온 파인드 배열 - int[] parent - 사이클 판단 4. 에지 개수 - int useEdge 5. 최소 가중치 합 결과 - int result 📍 실행 과정 그래프 에지 리스트, 유니온 파인드 배열 초기화 그래프 데이터를 가중치 기준으로 정렬 (참고) 가중치가 낮은 에지부터 연결 ..