백준 [1956] kotlin

[문제]

https://www.acmicpc.net/problem/1956

1956번: 운동

[풀이]

가장 최단거리인 사이클을 찾는 문제이므로, 

'하나의 정점'에서 '모든 정점'의 최단 경로를 찾는 다익스트라보다는, 

'모든 정점'에서의 '모든 정점'으로의 최단 거리를 구해야 하는 문제이다. 그러므로 플로이드 와샬로 풀 수 있는 문제이다.

다익스트라 -> '하나의 정점'에서 '모든 정점'의 최소 비용
플로이드 와샬 -> '모든 정점'에서의 '모든 정점'으로의 최소 비용

기본적인 알고리즘은 간단하다.

거쳐가는 경우가 핵심이다.

i에서 j로 이동을 할 때 최소 비용은 i -> j로 가는 최소 비용과,  i -> k + k -> j의 최소 비용중 더 작은 비용이 최소비용이 될 것이다.

 

그러므로, 입력으로 주어지는 각 정점의 이동 방향과 가중치를 배열에 저장한다.

이때 배열은 정점의 개수만큼 만들어지는데, 배열을 arr이라고 하면, arr[i][j]는 i에서 j로 가는 최소 비용이 되는 것이다.

 

for(k in 0 until V)
{
    for(i in 0 until  V)
    {
        for(j in 0 until V)
        {
            if(arr[i][k] == Int.MAX_VALUE || arr[k][j] == Int.MAX_VALUE ) continue
            if(arr[i][k] + arr[k][j] < arr[i][j]) arr[i][j] = arr[i][k] + arr[k][j]
        }
    }
}

위의 코드의 과정을 거쳐, 최소 비용을 갱신하면 된다.

 

가장 최단거리인 사이클을 찾는 방법은 간단하다

arr[i][j] + arr[j][i]의 합이 최소가 되는 값이 정답이다. 즉 i -> j의 최소 비용과 j -> i의 합이 최소를 찾는 것이다.

var ans = Int.MAX_VALUE
for(i in 0 until V-1)
{
    for(j in i+1 until V)
    {
        if(arr[i][j] == Int.MAX_VALUE || arr[j][i] == Int.MAX_VALUE) continue
        ans = min(ans, arr[i][j] + arr[j][i])
    }
}

이때 MAX_VALUE 인 경우를 제외시킨 이유는 MAX_VALUE는 갱신되어지지 않아, 즉 경로가 존재하지 않는 경우이기 때문이다.

이러한 과정을 거쳐 ans 값이 그래도 MAX_VALUE이면 사이클이 도는 경로가 없으므로, -1을 출력하고

그게 아니라면, ans가 정답이 된다.

[코드]

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

var V = 0
var E = 0
lateinit var arr : ArrayList<IntArray>
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    val tmp = br.readLine().split(" ").map{it.toInt()}
    V = tmp[0]
    E = tmp[1]

    arr = arrayListOf()
    repeat(V){
        i ->
        arr.add(IntArray(V){Int.MAX_VALUE})
        arr[i][i] = 0
    }
    repeat(E)
    {
        val tmp = br.readLine().split(" ").map{it.toInt()}
        arr[tmp[0]-1][tmp[1]-1] = tmp[2]
    }

    for(k in 0 until V)
    {
        for(i in 0 until  V)
        {
            for(j in 0 until V)
            {
                if(arr[i][k] == Int.MAX_VALUE || arr[k][j] == Int.MAX_VALUE ) continue
                if(arr[i][k] + arr[k][j] < arr[i][j]) arr[i][j] = arr[i][k] + arr[k][j]
            }
        }
    }
    var ans = Int.MAX_VALUE
    for(i in 0 until V-1)
    {
        for(j in i+1 until V)
        {
            if(arr[i][j] == Int.MAX_VALUE || arr[j][i] == Int.MAX_VALUE) continue
            ans = min(ans, arr[i][j] + arr[j][i])
        }
    }
    if(ans == Int.MAX_VALUE) bw.write("-1")
    else bw.write(ans.toString())
    bw.flush()
    bw.close()
}