글 읽기 - 런타임 오류가 뜹니다 ㅠㅠ (반례라도 알려주세요)

kelle111 2년 전 0

런타임 오류가 뜹니다. Union-Find 부분이 잘못인거 같긴한데 도통모르겠어요.. ㅠㅠ

반례라도 알려주시면 감사하겠습니다.

import java.util.*

var parent = IntArray(10001)

fun find(a:Int):Int {
    var x:Int = a
    if(parent[x] == x) return x
    while(parent[x] != x) x = parent[x]
    return x
}

fun union(a:Int, b:Int) {
    val rootA = find(a)
    val rootB = find(b)

    if(rootA != rootB) parent[rootA] = rootB
}

data class Point(val weight:Int,val start:Int,val end:Int)

fun main(args: Array<String>): Unit = with(Scanner(System.`in`)) {

    val n = nextInt()
    var pointX = arrayListOf<Pair<Int, Int>>()
    var pointY = arrayListOf<Pair<Int, Int>>()
    var pointZ = arrayListOf<Pair<Int, Int>>()

    for (i in 0..n-1){
        val a = nextInt();
        val b = nextInt();
        val c = nextInt();
        pointX.add(Pair(a,i));
        pointY.add(Pair(b,i));
        pointZ.add(Pair(c,i));
    }

    for (i in 0..n-1) {
        parent[i] = i
    }

    var sortedX = pointX.sortedBy { it.first }
    var sortedY = pointY.sortedBy { it.first }
    var sortedZ = pointZ.sortedBy { it.first }

    var points = arrayListOf<Point>()
    for (i in 0..n-2) {
        points.add(Point(sortedX[i+1].first - sortedX[i].first, sortedX[i].second, sortedX[i+1].second))
        points.add(Point(sortedY[i+1].first - sortedY[i].first, sortedY[i].second, sortedY[i+1].second))
        points.add(Point(sortedZ[i+1].first - sortedZ[i].first, sortedZ[i].second, sortedZ[i+1].second))

    }

    //크루스칼 알고리즘 
    var sortedPoint = points.sortedBy { it.weight }
    var total = 0

    for (sp in sortedPoint) {
        val weight = sp.weight
        val start = sp.start
        val end = sp.end

        if( find(start) != find(end)) {
            union(start, end)
            total += weight
        }

    }

    println(total)
}

sofod12 2년 전 0

이미 해결하셨겠지만,, 행성의 수는 100,000 개 입니다

var parent = IntArray(10001) 로 선언하셨네요 ㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

런타임 오류가 뜹니다 ㅠㅠ (반례라도 알려주세요)

kelle111 2년 전 0

sofod12 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말