1922 네트워크 연결

N개의 컴퓨터를 전부 하나의 네트워크로 묶으려고 할 때,
가장 작은 비용이 드는 경우를 고르는 문제이다.

딱봐도 간선문제인것이 그래프 문제라는 생각이 들었고,
그래프 알고리즘 중에서 프림알고리즘이 이 문제와 알맞는 알고리즘이라고 생각했다.
프림알고리즘은 자신의 영역과 이어진 간선중에서 가장 최소가 되는 간선을 골라서 자신의 영역을 늘려가는 방식이다. greedy 알고리즘의 일종인데, 보통 greedy 알고리즘은 최적의 결과를 낳지는 않는것으로 알려져 있으나, 이 알고리즘은 특이하게도 greedy 알고리즘이면서 최적의 결과를 낳는 알고리즘이다.

그래서 prim알고리즘을 적용하여 정답을 맞았으나..
TLE에 아주 아슬아슬하게 걸쳐있었다. 다른 사람의 소스는 매우 짧은 시간이 소요된것에 비해 내 방법은 매우 느린 결과를 보였다.
그래서 다른 사람의 소스를 살펴보니, 간선정보들을 오름차순으로 정렬하고 거기서부터 하나씩 뽑아서 연결하는 방법이었다.

그래프 알고리즘에 정렬을 사용한다는 생각은 못하고 있엇는데 역시 실력차이인것 같다.

소스