[kotlin 프로그래머스] 우주신과의 교감 1774 (with kotlin)

package com.chanhue.algorithm.백준.골드

import kotlin.math.sqrt

fun main() {
    // N: 우주신의 수, M: 이미 연결된 통로 수
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }

    // 각 우주신(혹은 황선자)의 좌표 정보를 저장하는 리스트
    val node = mutableListOf<Pair<Int, Int>>()

    // 이미 연결된 통로 정보 (정점 번호 쌍)
    val alreadyConnected = mutableListOf<Pair<Int, Int>>()

    // 좌표 입력 받기
    repeat(n) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() }
        node.add(Pair(x, y))
    }

    // 이미 연결된 노드 입력 받기
    repeat(m) {
        val (path1, path2) = readLine()!!.split(" ").map { it.toInt() }
        alreadyConnected.add(Pair(path1, path2))
    }

    // 간선 정보 저장: (거리 제곱, 정점1, 정점2)
    val edges = mutableListOf<Triple<Double, Int, Int>>()

    // 유니온 파인드를 위한 부모 배열 초기화 (1-based)
    val parent = IntArray(n + 1) { it }

    // 모든 정점 쌍에 대해 거리 제곱을 간선으로 저장
    for (i in 0 until n) {
        for (j in i + 1 until n) {
            val x = (node[i].first - node[j].first).toLong()
            val y = (node[i].second - node[j].second).toLong()
            val weight = (x * x + y * y).toDouble()  // 거리의 제곱을 저장
            edges.add(Triple(weight, i + 1, j + 1))  // 정점 번호는 1-based
        }
    }

    // 거리 제곱 기준으로 오름차순 정렬 (sqrt 하지 않음: 정렬 오차 방지)
    edges.sortBy { it.first }

    // 유니온 파인드: 루트 찾기
    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x])  // 경로 압축
        }
        return parent[x]
    }

    // 유니온 파인드: 두 집합을 합침
    fun union(x: Int, y: Int): Boolean {
        val xroot = find(x)
        val yroot = find(y)
        return if (xroot == yroot) {
            false  // 이미 같은 집합이면 union 실패
        } else {
            parent[yroot] = xroot  // y 루트를 x 루트에 붙임
            true
        }
    }

    // 이미 연결된 노드들에 대해 union 처리 (사이클 허용 없이 미리 연결)
    for ((a, b) in alreadyConnected) {
        union(a, b)
    }

    var sum = 0.0  // 최종 연결 거리 합계

    // 크루스칼 알고리즘: 간선들을 짧은 거리부터 추가
    for ((cost, a, b) in edges) {
        if (union(a, b)) {
            sum += sqrt(cost)  // 여기서만 sqrt 적용 (정밀도 확보)
        }
    }

    // 정답 출력: 소수점 둘째 자리까지
    println("%.2f".format(sum))
}

 

 

문제 푸는데 거리에 대한 자료형을 Int로 선언해서 통과를 하지 못한 것 같다 (4% 에서 계속 틀림)

    for (i in 0 until n) {
        for (j in i + 1 until n) {
            val x = (node[i].first - node[j].first).toLong()
            val y = (node[i].second - node[j].second).toLong()
            val weight = (x * x + y * y).toDouble()  // 거리의 제곱을 저장
            edges.add(Triple(weight, i + 1, j + 1))  // 정점 번호는 1-based
        }

x,y 에 대한 좌표를 long으로 선언해줘야함