[문제]
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
[입력 조건]
- 첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
- 둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
[출력 조건]
- 첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
해결한 방법
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.*
private lateinit var parent : IntArray
fun main(){
val br = BufferedReader(InputStreamReader(System.`in`))
var stk : StringTokenizer
val n = br.readLine().toInt()
parent = IntArray(n){ i -> i }
val starArray = Array(n){ Pair(0.0, 0.0) } // a별 x좌표, a별 y좌표
val edgeList : MutableList<Triple<Int, Int, Double>> = mutableListOf() // a별, b별, a->b cost
repeat(n){ i ->
stk = StringTokenizer(br.readLine())
starArray[i] = Pair(stk.nextToken().toDouble(), stk.nextToken().toDouble())
repeat(i){ j ->
val dist = getDistance(starArray[i], starArray[j]) // 다른 별과 거리 저장
edgeList.add(Triple(j, i, dist))
}
}
edgeList.sortWith( compareBy{ it.third } ) // 비용을 기준으로 정렬
var totalCost = 0.0
edgeList.forEach{
val a = it.first
val b = it.second
val cost = it.third
if(findParent(a) != findParent(b)){ // 크루스칼 부모가 다르면 유니온
union(a, b)
totalCost += cost
}
}
print(totalCost)
}
fun getDistance(i : Pair<Double, Double>, j : Pair<Double, Double>): Double{
return floor(hypot((i.first - j.first), (i.second - j.second)) * 100 ) / 100
}
fun findParent(x : Int) : Int{
if(parent[x] == x) return x
parent[x] = findParent(parent[x])
return parent[x]
}
fun union(a : Int, b: Int) {
val A = findParent(a)
val B = findParent(b)
if (A == B) return
parent[B] = A
}별의 좌표를 입력받을 때 마다 이전에 입력 받았던 별과 간선을 연결한다. 별의 갯수 최대는 100개이며, 최대 간선의 갯수는 총 5050개이다. 별의 번호는 인덱스로 매겨지며, 거리와 함께 간선 리스트(edgeList)에 넣는다. 거리를 기준으로 정렬하며, 꺼낸 두 별의 루트 노드가 다른 경우 연결되어 있지 않다고 가정하며, 결과 값에 거리를 더한다.
