[백준 kotlin] 1956 운동

문제

 

그래프 중 사이클을 찾는 문제이다.

---

풀이

그래프 알고리즘 중 사이클을 고려해야 하는 문제이다.

기존에 자주사용하는 다익스트라의 경우 사이클은 감지하지 못하므로 다른 알고리즘을 사용해야 한다. 

 

따라서 플루이드 워셜 알고리즘을 사용하였다.

 

const val INF = Int.MAX_VALUE / 2

먼저 최대값을 정의하였다. 최대값은 MAX_VALUE에 2를 나누어 주었는데 그 이유는 overflow를 방지하기 위함이다.

 

val (V, E) = readLine().split(" ").map { it.toInt() }
    val node = Array(V + 1) { IntArray(V + 1) {INF} }
    repeat(E) {
        val (a, b, c) = readLine().split(" ").map { it.toInt() }
        node[a][b] = c
}

이후 노드의 정보를 입력받는다. 

왕복이 불가능하므로 간선은 [a][b] = c 형태로만 입력받았다.

 

for (k in 1..V) {
    for (i in 1..V) {
        for (j in 1..V) {
            node[i][j] = min(node[i][j], node[i][k] + node[k][j])
        }
    }
}

 

다음으로 플로이드 워셜을 사용하여 간선사이의 최솟값을 계산하였다.

 

이렇게 계산 후에 간선은 2차원 배열로 자기자신으로부터 해당 노드까지의 최단거리를 가지는 배열이 저장된다.

 

따라서 특정 노드로부터의 사이클은 해당 노드로부터 해당 노드까지의 거리를 측정하면 된다.

var res = INF

for (i in 1..V) {
    res = min(res, node[i][i])
}

if (res == INF) {
    println(-1)
} else {
    println(res)
}

따라서 다음과 같이 모든 노드에 대해서 사이클이 있는지 확인하며 있을경우 그 중 최소값을 출력하는 코드를 작성하였다.

---

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

const val INF = Int.MAX_VALUE / 2

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

    val (V, E) = readLine().split(" ").map { it.toInt() }

    val node = Array(V + 1) { IntArray(V + 1) {INF} }
    repeat(E) {
        val (a, b, c) = readLine().split(" ").map { it.toInt() }
        node[a][b] = c
    }

    for (k in 1..V) {
        for (i in 1..V) {
            for (j in 1..V) {
                node[i][j] = min(node[i][j], node[i][k] + node[k][j])
            }
        }
    }

    var res = INF

    for (i in 1..V) {
        res = min(res, node[i][i])
    }

    if (res == INF) {
        println(-1)
    } else {
        println(res)
    }
}