[백준] 최단경로 (1753)(Kotlin)

원본 문제 : https://www.acmicpc.net/problem/1753

 

<첫번째> 실패 - 메모리초과(Adjacency Matrix)

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){

    val str = readLine().split(" ")
    val V = str[0].toInt()
    val E = str[1].toInt()
    val start = readLine().toInt()

    var graph: Array<IntArray> = Array( V+1 ) { IntArray( V+1 ) }

    for ( i in 1 until E+1 ) {
        val net = readLine().split(" ")
        val a = net[0].toInt()
        val b = net[1].toInt()
        val c = net[2].toInt()
        graph[a][b] = c
    }

    var distance: IntArray = IntArray( V+1 )
    var check: BooleanArray = BooleanArray( V+1 )

    for ( i in 1 until V+1 ) {
        distance[i] = Int.MAX_VALUE
    }

    distance[start] = 0
    check[start] = true

    for ( i in 1 until V+1 ) {
        if ( !check[i] && graph[start][i] != 0 ) {
            distance[i] = graph[start][i]
        }
    }

    for ( a in 0 until V/2 - 1 ) {
        var min = Int.MAX_VALUE
        var min_index = -1

        for ( i in 1 until V+1 ) {
            if ( !check[i] && distance[i] != Int.MAX_VALUE ) {
                if ( min > distance[i] ) {
                    min = distance[i]
                    min_index = i
                }
            }
        }

        check[min_index] = true

        for ( i in 1 until V+1 ) {
            if ( !check[i] && graph[min_index][i] != 0 ) {
                if ( distance[i] > distance[min_index] + graph[min_index][i] ) {
                    distance[i] = distance[min_index] + graph[min_index][i]
                }
            }
        }
    }

    for ( i in 1 until V+1 ) {
        if ( distance[i] == Int.MAX_VALUE)
            println("INF")
        else
            println("${distance[i]}")
    }
}

 

<두번째> 성공 - Adjacency List

import java.io.*
import java.util.*
import kotlin.collections.ArrayList

class Node : Comparable<Node> {

    var index: Int = 0
    var distance: Int = 0

    constructor(index: Int, distance: Int) {
        this.index = index
        this.distance = distance
    }

    override fun compareTo(other: Node): Int {
        return this.distance - other.distance
    }

}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    val str = readLine().split(" ")
    val v = str[0].toInt()
    val e = str[1].toInt()
    val start = readLine().toInt()
    val list: ArrayList<PriorityQueue<Node>> = ArrayList( v+1 )

    for ( i in 0 until v+1 ) {
        list.add(PriorityQueue<Node>())
    }

    for ( i in 0 until e ) {
        val net = readLine().split(" ")
        val a = net[0].toInt()
        val b = net[1].toInt()
        val c = net[2].toInt()
        list[a].add(Node(b,c))
    }


    var distance: IntArray = IntArray( v+1 )
    var check: BooleanArray = BooleanArray( v+1 )
    val pq: PriorityQueue<Node> = PriorityQueue<Node>()

    Arrays.fill(distance, Int.MAX_VALUE)

    distance[start] = 0
    pq.add(Node(start, 0))

    while ( !pq.isEmpty() ) {
        val now: Int = pq.poll().index

        if (check[now]) continue
        check[now] = true

        for ( node in list[now] ) {
            if ( distance[node.index] > distance[now] + node.distance ) {
                distance[node.index] = distance[now] + node.distance
                pq.add(Node(node.index, distance[node.index]))
            }
        }
    }

    for ( i in 1 until v+1 ) {
        if (distance[i] == Int.MAX_VALUE)
            println("INF")
        else
            println("${distance[i]}")
    }
}