공부공간

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. � www.acmicpc.net 3차원 공간에서 모든 지점의 최소스패닝트리를 구하는 문제이다. 최악의 경우 N이 10만개일 때, 자신을 제외한 99999개를 구해야한다. 10만*10만의 연산을 통하여 간선길이를 정렬하면 메모리초과와 시간초과가나기때문에, 정렬을 통하여 m번째 노드는 m-1 , m+1번째만 계산을 통한다. ...m-2, m+2 ...은 정렬이 되어있기 때문에 최소가 보장되지 않는다. 이를 X ,Y, Z 에대해서 한..

https://www.acmicpc.net/problem/6497 6497번: 전력난 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈�� www.acmicpc.net 모든 가로등의 합에서 최소의 가로등의 비용으로 모든 노드를 연결해야하기때문에 MST문제와 동치이다. 크루스칼 알고리즘으로 해결하였다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTok..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 최소 컴포넌트의 크기가 2개가 되야 하므로, 초기 N개의 컴포넌트에서 Kruskal 알고리즘으로 성공적으로 Union되었을시, 컴포넌트의 개수를 감소시킨다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.Pri..