[백준] 파티 (1238)(Kotlin)

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

문제 참고(플로이드와샬) : https://pangsblog.tistory.com/91

 

<첫번째> 플로이드 와샬

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

var n: Int = 0
var x: Int = 0
var route: Array<IntArray> = arrayOf()

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

    val nmx = readLine().split(" ")
    n = nmx[0].toInt()
    var m = nmx[1].toInt()
    x = nmx[2].toInt()

    route = Array( n+1 ) { IntArray( n+1 ) }

    for ( i in 1 until n+1 ) {
        for ( j in 1 until n+1) {
            if ( i == j)
                continue
            else
                route[i][j] = Int.MAX_VALUE
        }
    }

    while ( m-- > 0 ) {

        val str = readLine().split(" ")
        val start = str[0].toInt()
        val dest = str[1].toInt()
        val cost = str[2].toInt()

        route[start][dest] = cost
    }

    floydwarshall()

    var result: Int = 0

    for ( i in 0 until n+1 ) {
        result = Math.max(result, route[i][x] + route[x][i])
    }

    println(result)


}

fun floydwarshall() {

    for ( k in 1 until n+1 ) {
        for ( i in 1 until n+1 ) {
            for ( j in 1 until n+1 ) {
                if ( route[i][k] + route[k][j] > 0)
                    route[i][j] = Math.min(route[i][j], route[i][k] + route[k][j])
            }
        }
    }

}

 

<두번째> 다익스트라(adjacency list)

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

var n: Int = 0
var x: Int = 0
var list: ArrayList<PriorityQueue<Node>> = ArrayList<PriorityQueue<Node>>()
var distance: IntArray = intArrayOf()

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 nmx = readLine().split(" ")

    n = nmx[0].toInt()
    val m: Int = nmx[1].toInt()
    x = nmx[2].toInt()

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

    for ( i in 0 until m ) {
        val str = readLine().split(" ")
        val start = str[0].toInt()
        val end = str[1].toInt()
        val cost = str[2].toInt()

        list[start].add(Node(end, cost))
    }

    distance = IntArray( n+1 )
    var route: Array<IntArray> = Array( n+1 ) { IntArray( n+1 ) }

    for ( i in 1 until n+1 ) {
        dijkstra(i)
        for ( j in 1 until n+1 ) {
            route[i][j] = distance[j]
        }
    }

    var result: Int = 0
    for ( i in 1 until n+1 ) {
        result = Math.max(result, route[i][x] + route[x][i])
    }

    println(result)

}

fun dijkstra(start: Int) {

    val pq: PriorityQueue<Node> = PriorityQueue<Node>()

    Arrays.fill(distance, Int.MAX_VALUE)
    var check: BooleanArray = BooleanArray( n+1 )

    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]))
            }
        }
    }

}