[BOJ] 백준 4386번 : 별자리 만들기 (JAVA)

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

 

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

 

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

 

 

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

 

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

 

 

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

 

 

풀이

크루스칼 알고리즘을 사용하여 풀 수 있는 문제였습니다.

 

문제에서는 바로 두 정점 간의 비용에 대한 정보를 주지 않고, 2차원 좌표만 주었습니다.

n은 최대 100으로 값이 작기때문에 2중 반복문을 사용하여 모든 별들 간의 거리를 구하고, 간선의 정보를 edgeList에 넣으면 됩니다.

 

그리고 전형적인 크루스칼 알고리즘 방식을 사용하여 가중치의 합을 구하시면 됩니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.