mondegreen

최소 비용을 구하는 문제이다. 먼저 각 섬의 루트노드를 저장할 배열을 선언한다. 이 때 초기 값은 각자의 인덱스 값이다. 즉, 각자가 루트노드인 것이고 각자의 집합에 속해있는 것이다. 그 다음 건설 비용이 적은 순서대로 먼저 정렬해준 후 순서대로 연결을 해본다. 이 때 연결하기 전 두 섬의 연결되어 있는지는 루트 노드를 찾아서 비교한다. 만약 다르다면 다리 연결에 드는 비용을 정답 변수에 더해주고 유니언 메소드를 통해 한쪽 루트노드를 다른 한 쪽으로 변경해서 합쳐준다. 같을 때 다리를 놓는다면 사이클이 생겨 비효율적이고 최소 비용이 될 수 없다. 이 작업을 반복하며 다리의 갯수가 n-1개 일 때 작업을 완료하면 된다. n개를 연결하는 최소 갯수는 n-1개 이기 때문이다. import java.util.*..