백준 [1647] kotlin

문제

https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

풀이

문제의 조건을 보면,

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

두 가지 조건이 있습니다. 

두번째 조건을 보면, 최소 신장 트리를 찾아내야 하는 문제입니다. 그리고 가중치의 경우에는 첫번째 조건을 통해 알 수 있습니다. 곧 두 별 사이의 거리가 가중치입니다.

 

최소 신장 트리를 구하는 방법은 두 가지가 있습니다. (Kruskal, Prim) 

 

저는 Kruskal 알고리즘을 통해 해결하였습니다.

 

가장 먼저, 모든 별들 사이의 가중치를 구해야 합니다.

이는 두 점 사이의 거리 공식을 통해 구하면 쉽게 해결할 수 있습니다.

fun cal(x1 : Float, y1 : Float, x2 : Float, y2 : Float) : Float {
    return sqrt((x1 - x2).pow(2) + (y1 - y2).pow(2))
}

 

별 들의 정보를 입력 받고, 별들의 정보를 쉽게 입력받은 순서대로 이름을 설정하였습니다.

부모에 대한 정보 p 배열을 만들어줍니다. 초기값은 자기 자신으로 설정합니다.

p = IntArray(N){i -> i}

 

그리고 입력받은 별들의 정보를 통해 가중치를 계산하여 그 결과를 우선순위 큐 stars에 저장을 합니다. 

이 때 세번째 즉 가중치를 기준으로 정렬을 합니다.

val comp : Comparator<Triple<Int, Int, Float>> = compareBy { it.third }

stars = PriorityQueue(comp)
for(i in arr.indices){
    for(j in i+1 until arr.size) {
        stars.add(Triple(i, j, cal(arr[i].first, arr[i].second, arr[j].first, arr[j].second)))
    }
}

 

그리고 부모가 일치하는지 찾는 find 함수

그리고 부모를 찾는 getParent 함수

그리고 union 함수를 각각 만들어줍니다.

fun find(a : Int, b : Int) : Boolean {
    val a = getParent(a)
    val b = getParent(b)
    if(a == b) return true
    return false
}
fun getParent(x : Int) : Int
{
    if(x == p[x]) return x
    p[x] = getParent(p[x])
    return p[x]
}

fun unionParent(a : Int, b : Int)
{
    val na = getParent(a)
    val nb = getParent(b)
    if(na > nb) p[na] = p[nb]
    else p[nb] = p[na]
}

 

마지막으로, 만들어진 가중치 정보를 이용하여 최소 신장트리를 구합니다. 이때 필요한 것은 가중치의 합이므로, ans 라는 변수를 만들어 

find 함수의 결과가 false 면 (부모가 다름) , 두 별을 연결할 수 있으므로, union을 통해 연결하고 가중치를 ans에 더해줍니다.

 

var ans = 0.0
while(stars.isNotEmpty())
{
    val tmp = stars.poll()
    if(!find(tmp.first, tmp.second)){
        ans += tmp.third
        unionParent(tmp.first, tmp.second)
    }
}

 

더 이상 가중치를 확인할 stars가 없다면, 배열을 빠져나오고, ans에 최소 신장 트리의 가중치의 합이 담겨지게 됩니다. 끝.

코드

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.PriorityQueue
import kotlin.math.pow
import kotlin.math.sqrt

var N = 0
lateinit var stars : PriorityQueue<Triple<Int,Int,Float>>
lateinit var p : IntArray
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))

    N = br.readLine().toInt()
    p = IntArray(N){i -> i}
    val arr = mutableListOf<Pair<Float, Float>>()
    repeat(N){
        val tmp = br.readLine().split(" ").map { it.toFloat() }
        arr.add(Pair(tmp[0], tmp[1]))
    }

    val comp : Comparator<Triple<Int, Int, Float>> = compareBy { it.third }

    stars = PriorityQueue(comp)
    for(i in arr.indices){
        for(j in i+1 until arr.size) {
            stars.add(Triple(i, j, cal(arr[i].first, arr[i].second, arr[j].first, arr[j].second)))
        }
    }
    var ans = 0.0
    while(stars.isNotEmpty())
    {
        val tmp = stars.poll()
        if(!find(tmp.first, tmp.second)){
            ans += tmp.third
            unionParent(tmp.first, tmp.second)
        }
    }
    bw.write(ans.toString())
    bw.flush()
    bw.close()

}
fun find(a : Int, b : Int) : Boolean {
    val a = getParent(a)
    val b = getParent(b)
    if(a == b) return true
    return false
}
fun getParent(x : Int) : Int
{
    if(x == p[x]) return x
    p[x] = getParent(p[x])
    return p[x]
}

fun unionParent(a : Int, b : Int)
{
    val na = getParent(a)
    val nb = getParent(b)
    if(na > nb) p[na] = p[nb]
    else p[nb] = p[na]
}
fun cal(x1 : Float, y1 : Float, x2 : Float, y2 : Float) : Float {
    return sqrt((x1 - x2).pow(2) + (y1 - y2).pow(2))
}