백준 [10021] kotlin

[문제]

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

10021번: Watering the Fields

[풀이]

시간 제한과 메모리 제한이 상당히 빡빡한 문제였다.

문제를 처음 보았을 때,

입력으로 받은 모든 좌표 사이의 유클리드 값을 우선순위 큐에 저장을 하고,

크루스칼 알고리즘을 이용해서 풀면 되는 간단한 문제인줄 알았다.

 

데이터 클래스를 직접 구현하고, 해당 데이터 클래스의 Comparable도 직접 구현했었지만, 계속해서 시간초과가 발생했다.

 

• 이를 해결한 방법은, 다음과 같다.입력으로 받은 모든 좌표 사이의 유클리드 값을 얻는 과정에서 이중 for문을 돌 때  모든 범위에서 for문을 돌리고 i와 j가 같다면 continue하는 방식으로 중복된 좌표를 피했다. 이러한 방법보다, 아래와 같이 하는 방법이 더 효율적이다.

for(i in 0 until arr.size)
{
    for(j in i until arr.size)
    {
    }
}

• 직접 데이터 클래스를 구현해주는 것 대신에 Triple을 사용했다.

최대한 모든 방법을 사용해서 통과한 문제이다.

[코드]

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

var C = 0
lateinit var S : IntArray
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    val arr = arrayListOf<Pair<Int, Int>>()
    val tmp = br.readLine().split(" ").map{it.toInt()}

    C = tmp[1]
    S = IntArray(tmp[0]){i -> i}
    repeat(tmp[0])
    {
        val tmp = br.readLine().split(" ").map { it.toInt() }
        arr.add(Pair(tmp[0],tmp[1]))
    }

    val comparable : Comparator<Triple<Int,Int,Int>> = compareBy { it.third }
    var E = PriorityQueue(comparable)

    for(i in 0 until arr.size)
    {
        for(j in i until arr.size)
        {
            val tmp = (arr[i].first - arr[j].first).toFloat().pow(2)  + (arr[i].second - arr[j].second).toFloat().pow(2)
            if(tmp >= C) E.offer(Triple(i,j,tmp.toInt()))
        }
    }
    var ans = 0
    var count = 0
    while (E.isNotEmpty())
    {
        val tmp = E.remove()
        if(find(tmp.first, tmp.second)){
            ans += tmp.third
            count++
            unionParent(tmp.first, tmp.second)
        }
    }
    if(count < tmp[0]-1) bw.write("-1")
    else bw.write(ans.toString())
    bw.flush()
    bw.close()
}

fun getParent(a : Int) : Int
{
    if(S[a] == a) return a
    S[a] = getParent(S[a])
    return S[a]
}

fun unionParent(a : Int, b : Int)
{
    val a = getParent(a)
    val b = getParent(b)
    if(a < b) S[b] = a
    else S[a] = b
}

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