[백준][Kotlin]16562번 친구비

해당 문제는 유니온파인드를 이용하여 작성할 수 있습니다.

코드를 작성하기 위한 포인트로는 친구들의 관계를 입력 받을 때 union 함수를 이용하여 미리 친구들의 관계를 합치는 것과 합칠 때 해당 둘 중 친구비가 더욱 적은 친구를 대표노드로 만들어 놓는 것입니다.

그리고 모든 입력을 받은 후 본인(이준석,0)과 union 함수를 이용하여 자신과 다른 대표 노드를 가지고 있는 친구들의 한하여 비교 및 친구비 계산을 하여 출력하면 됩니다.

하기는 제가 작성한 코드와 제출 결과 입니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

lateinit var friend: IntArray
lateinit var money: IntArray

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    //val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    val n = st.nextToken().toInt()
    val m = st.nextToken().toInt()
    val k = st.nextToken().toInt() // 가지고 있는 돈

    friend = IntArray(n+1){i: Int -> i }
    money = IntArray(n+1){0}
    st = StringTokenizer(br.readLine())
    for(i in 1 .. n){
        money[i] = st.nextToken().toInt()
    }

    for(i in 1 .. m){
        st = StringTokenizer(br.readLine())
        var fr1 = st.nextToken().toInt()
        var fr2 = st.nextToken().toInt()
        union(fr1,fr2)
    }

    var sum = 0
    for(i in friend){
        if(0 != find(i)){
            sum += money[find(i)] // 대표 노드의 돈을 확인 후 +연산을 해야함~!
            union(0,i)
        }
    }

    if(sum > k) println("Oh no")
    else println(sum)

    //bw.flush()
    //bw.close()
}

fun find(a:Int):Int{
    if(friend[a] == a) return a
    friend[a] = find(friend[a])
    return friend[a]
}

fun union(a:Int,b:Int){
    var x = find(a)
    var y = find(b)
    if(x != y){
        if(money[x] <= money[y]){
            friend[y] = x
        } else {
            friend[x] = y
        }
    }
}