공부공간

www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 클래스로 묶고 별자리 간 거리를 계산해서 우선순위 큐에 넣는다. 거리가 짧은 별자리들의 쌍이 항상 나오므로, 크루스칼 알고리즘으로 MST를 완성한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util...

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제집에서 순서가 존재하기때문에 차수를 고려한 위상정렬을 진행해준다. 다만, 문제 번호가 1-N 까지 문제중에서 차수가 0 이되었을때에 우선순위를 부여해야한다 ( 쉬운문제 부터 푼다 ) 따라서, 우선순위큐에 문제번호가 낮은 차수가 0 인 노드부터 처리해주자 import java.io.BufferedReader; import java.io.InputStreamReader; impor..