[백준] 운동 (1956)(kotlin)

문제 설명

백준 1956번 문제 링크

입력 및 출력

» 입력

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다. (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.

» 출력

첫째 줄에 최소 사이클의 도로 길이의 합을 출력한다. 운동 경로를 찾는 것이 불가능한 경우에는 -1을 출력한다.

예제 입출력(테스트케이스)

입력	출력
3 4 1 2 1 3 2 1 1 3 5 2 3 2	3

문제 풀이1

fun main() = with(System.`in`.bufferedReader()) {
    val (V, E) = readLine().split(" ").map { it.toInt() }
    // c의 최댓값은 400 * 10_000
    val matrix = Array(V + 1) { IntArray(V + 1) { 40_000_001 } }

    repeat(E) {
        val (a, b, c) = readLine().split(" ").map { it.toInt() }
        // (단방향) a에서 b로 가는 비용이 c
        matrix[a][b] = c
    }

    for (i in 1..V) for (j in 1..V) for (k in 1..V) {
        // i -> j로 갈 때, i -> k -> j로 k를 경유해서 가는 비용과 비교하여
        if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
            // k로 경유해서 가는 비용이 i -> j로 가는 최소비용보다 작으면 그 최소비용을 갱신
            matrix[i][j] = matrix[i][k] + matrix[k][j]
        }
    }

    // 비용인 c가 가질 수 있는 최댓값으로 최솟값을 초기화
    var min = 40_000_001
    for (i in 1..V) for (j in 1..V) {
        // i -> j -> i, i에서 시작해서 j를 경유해 i로 복귀하는 값들 중 최솟 비용을 탐색
        min = Math.min(min, matrix[i][j] + matrix[j][i])
    }

    // 최소비용이 갱신되지 않았으면, 해당하는 경로가 없으므로 -1
    // 그렇지 않으면 최솟값을 출력
    if (min == 40_000_001) println(-1)
    else println(min)
}