[백준 11657번][Kotlin] 타임머신

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

11657번: 타임머신

 

난이도 : 골드 4
태그 : 그래프 이론, 벨만-포드

 

 

설명

1번 도시에서 출발해 나머지 도시로 가는 최단경로를 구하는 문제입니다.

다만, 음의 간선이 존재하므로 다익스트라는 사용하기 어렵습니다.

 

음의 간선이 있다는 것을 보고, 어떻게 풀어야하나... 하며 최단경로 알고리즘을 찾아보다가,

음의 간선일때의 쓰는 최단경로 알고리즘인 벨만-포드 알고리즘이 있더군요. 지식이 늘었습니다.

 

 

벨만 - 포드 알고리즘

벨만 포드의 동작구조는 다음과 같습니다.

 

1. 출발 노드 선택
2. 최단거리 테이블 초기화
3. 모든 간선을 확인해보며 각 간선을 거쳐, 더 적은 cost일때 다른 노드로 가는 비용을 갱신
   1. 만약 음수 간선이 순환한다면, 즉 사이클이 발생한다면 최단 경로가 음의 무한으로 수렴하는 현상 발생
   2. 음의 사이클이 발생되는지 확인하고 싶다면 3번을 한 번 더 수행한다. 이때 테이블이 갱신된다면 음의 사이클이 있는 것이다

 

벨만 포드는 기본적으로 다익스트라의 해를 포함하며, 시간복잡도가 다익스트라보다 크기에,

음의 간선이 없을 땐 다익스트라를 쓰시는 것이 좋습니다.

 

다익스트라는 양의 간선만 존재할 때 쓰기 적합한 알고리즘

플로이드-워셜은 모든 노드쌍에 대해 쓰기 적합한 알고리즘

벨만-포드는 음의 간선이 존재할 때 쓰기 적합한 알고리즘으로 정리할 수 있겠네요.

 

 

소스코드

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

data class BUS(var from: Int, var to: Int, var weight: Int)

val MAX_VALUE = 10000000
lateinit var distance: Array<Long>
lateinit var busList: Array<BUS?>
var n = 0
var m = 0

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

    val nm = br.readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]

    busList = Array(m) { null }
    distance = Array(n + 1) { MAX_VALUE.toLong() } // 최단 거리 테이블. 최대값으로 초기화

    // 간선 정보 입력
    repeat(m) {
        val line = br.readLine().split(" ").map { it.toInt() }
        busList[it] = BUS(line[0], line[1], line[2])
    }

    // 시간을 무한히 오래 전으로 되돌릴 수 있음 (음의 사이클 발생)
    if (bellmanFord(1)) {
        println(-1)
    } else {
        for (i in 2..n) {
            // 가는 경로가 없을 때 -1 출력
            if (distance[i] == MAX_VALUE.toLong()) {
                println(-1)
            } else {
                println(distance[i])
            }
        }
    }
}


fun bellmanFord(start: Int): Boolean {
    distance[start] = 0 // 시작 노드로 가는 비용은 0

    for (i in 1 until n) {
        for (j in 0 until m) {
            val targetBus = busList[j]!!

            // 현재 수행중인 간선을 타고 다른 노드로 가는 cost 가 더 적을 경우 테이블 갱신
            if (distance[targetBus.from] != MAX_VALUE.toLong() && distance[targetBus.to] > distance[targetBus.from] + targetBus.weight) {
                distance[targetBus.to] = distance[targetBus.from] + targetBus.weight
            }
        }
    }

    // 만약 이때 경로가 더 짧은 경로로 갱신된다면 음의 사이클이 발생한 것
    for (i in 0 until m) {
        val targetBus = busList[i]!!
        if (distance[targetBus.from] != MAX_VALUE.toLong() && distance[targetBus.to] > distance[targetBus.from] + targetBus.weight) return true
    }
    return false
}

distance를 Int형 배열로 선언했다가, 오버플로우가 발생해 출력초과를 받았습니다

Long 타입으로 바꿔 다시 제출했더니 통과했네요.

 

 

후기

다익스트라와 플로이드-워셜이 아닌 새로운 최단경로 알고리즘인 벨만-포드를 접했던 문제였는데요.

음의 간선일때도 사용할 수 있다는 것이 꽤 신기하네요.