<baekjoon> 별자리 만들기

풀이

선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구해야 하므로 최소스패닝 트리 알고리즘을 사용하였다.(크루스칼)

 

크루스칼 알고리즘을 사용하기 위해서는 union, find라는 메소드가 필요하고 각 좌표들이 어느 좌표를 가리키는지를 확인하기 위해 Edge라는 클래스를 생성하였다.

 

우선 입력받은 좌표들을 Point클래스로 객체화 하여 List에 넣어주었다. 동시에 각 좌표들을 스스로를 가리키며 루트노드가 된다.(초기단계)

 

그리고 Edge자료형의 List를 추가로 만들어서 Point객체의 각 값들을 이용하여 최소 값을 구하였다(특정 좌표에서 다른 좌표로 이동할 때 비용).

 

그 다음으로는  Collections.sort를 이용하여 최소비용이 가장 적게 드는 순서대로 정렬하였다.

 

마지막으로 각 좌표들을 연결해주면서 최소비용을 구하였다.(여기서 find함수와 union함수를 이용하여 연결되지 않은 두 좌표를 연결해준다.) 

 

결과