[백준 13141] Ignition (Kotlin)

🏆 문제 난이도
- Platinum V

🔗 문제 링크
https://www.acmicpc.net/problem/13141

📝 문제 분석 & 접근

플레 치고는 어렵지 않은 문제입니다.

플로이드-와샬 알고리즘을 사용해서 모든 정점 쌍 간의 최단 거리를 구해줍니다.

플로이드-와샬을 사용하는 이유는, 모든 점에서 다른 모든 점들까지의 최단거리를 모두 구해야 하기 때문입니다.

 

각 노드의 최단거리를 구한 다음에는 각 정점 별로 타는데 가장 오래 걸리는 시간들 중에서 가장 작은 값을 구하면 됩니다.

---

✨ 핵심 아이디어

시작점 i에서 불이 붙기 시작해서 어떤 도로 j (start, end)를 태우는 데 걸리는 시간은 maxLength = dist[i][start] + dist[i][end] + length[j]로 계산할 수 있습니다.

• dist[i][start] : 정점 i에서 도로 j의 시작점 start까지 가는 최단 시간
• dist[i][end] : 정점 i에서 도로 j의 끝점 end까지 가는 최단 시간
• length[j] : 도로 j의 길이 (불이 붙는 시간)

불이 동시에 붙는다고 해서 도로를 태우는데 걸리는 시간을 구할 때 2로 나눠주고 비교하지 않습니다!!
일단, 가장 긴 도로를 구하고, 걸리는 시간은 나중에 출력할 때 따로 구해줍니다.

 

즉, 정점 i에서 모든 도로에 불을 붙이는 데 걸리는 시간을 계산하고, 이 중에서 가장 오래 걸리는 시간을 찾습니다.

모든 도로를 다 태우려면 이 가장 긴 시간만큼 기다려야 하기 때문입니다.

모든 정점 i에 대해 이 과정을 반복하면서 가장 짧은 maxLength를 찾아내면 그것이 바로 모든 도로를 태우는 최소 시간이 됩니다.

 

마지막으로, 문제에서 구하는 것은 모든 도로가 불타는 데 걸리는 총 시간이므로, 우리가 구한 minLength를 2로 나눠야 합니다.

왜냐하면 불은 양방향에서 동시에 붙기 때문에 실제로는 길이의 절반만 태워도 되기 때문입니다.

만약 minLength가 홀수라면 5를 붙여 소수점 첫째 자리까지 정확하게 출력해 주면 됩니다.

---

💻 코드

import java.io.StreamTokenizer
import kotlin.math.max
import kotlin.math.min

const val INF = 1_000_000_000_000_000L // 10^15 => 이거 걍 Long.MAX_VALUE로 하면 오버플로우 발생해서 계산값이 갑자기 음수로 나올 수도 있음.

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun StreamTokenizer.nextInt(): Int{
        nextToken()
        return nval.toInt()
    }
    fun StreamTokenizer.nextLong(): Long{
        nextToken()
        return nval.toLong()
    }

    val n = nextInt()
    val m = nextInt()

    val dist = Array(n + 1) { LongArray(n + 1) { INF } }
    val start = IntArray(m + 1)
    val end = IntArray(m + 1)
    val length = LongArray(m + 1)

    for(i in 1..n) dist[i][i] = 0 // diagonal을 0으로 변경

    for (i in 1..m) {
        start[i] = nextInt()
        end[i] = nextInt()
        length[i] = nextLong()
        dist[start[i]][end[i]] = min(dist[start[i]][end[i]], length[i])
        dist[end[i]][start[i]] = min(dist[end[i]][start[i]], length[i])
    }

    // 플로이드 와샬
    for (k in 1..n) {
        for (i in 1..n) {
            for (j in 1..n) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            }
        }
    }

    // 가장 긴거 먼저 고르고, 계산은 나중에
    var minLength = INF
    for (i in 1..n) {
        var maxLength = 0L
        for (j in 1..m) {
            maxLength = max(maxLength, dist[i][start[j]] + dist[i][end[j]] + length[j])
        }
        minLength = min(minLength, maxLength)
    }

    // 계산
    println("${minLength / 2}.${if(minLength % 2 == 1L) 5 else 0}")
}