매일 조금씩

문제 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 MST 만드는 문제로 보여서 크루스컬 알고리즘으로 풀었다. 가중치가 적은 간선부터 사이클이 만들어지지 않을 경우, 연결해 나간다. 소스코드 import java.util.*; class Edge implements Comparable{ int nodeA; int nodeB; int weight; public Edge(int nodeA, int nodeB, int weight){ this.nodeA = nodeA; this.nodeB = nodeB; ..

#문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net #풀이 Kruscal 알고리즘을 이용하여 문제를 풀었다. 두 정점 간의 비용이 주어지지 않기 때문에 간선 정보를 직접 만들어줘야 한다. 이중 For문으로 모든 정점을 순회하면서 쌍을 만들어 Edge를 생성해주었고 이때 distance를 계산해서 가지고 있게 했다. (다행히 별의 개수가 100개로 제한되어 있기 때문에 시간 초과 문제는 없었다.) 그리고 EdgeList를 distance 오름차..