[백준/BOJ] 1240번: 노드사이의 거리

문제

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

1240번: 노드사이의 거리

해설

n - 1개의 노드 사이의 거리가 주어지고, m개의 노드 사이의 거리를 구해야 한다.

크루스칼 알고리즘, dfs 등 여러 방법이 있을 수 있지만, 나는 문제를 보자마자 플로이드 와샬 알고리즘을 떠올렸다.

n이 크지 않으므로 간단히 모든 노드 사이의 최소 거리를 구해놓고, 구하고자 하는 노드 사이의 거리를 출력하면 된다라고 생각했다.

또한 플로이드 와샬 알고리즘은 구현 방법도 쉽기 때문에 상당히 쉽게 풀은 문제였다.

코드

import kotlin.math.min

private lateinit var arr: Array<IntArray>
private const val INF = 987654321

fun main() = with(System.`in`.bufferedReader()) {
    val (nodeCnt, pairCnt) = readLine().split(" ").map { it.toInt() }

    arr = Array(nodeCnt + 1) { IntArray(nodeCnt + 1) { INF } }

    repeat(nodeCnt - 1) {
        val (node1, node2, distance) = readLine().split(" ").map { it.toInt() }
        arr[node1][node2] = distance
        arr[node2][node1] = distance
    }

    floyd(nodeCnt)

    repeat(pairCnt) {
        val (node1, node2) = readLine().split(" ").map { it.toInt() }
        println(arr[node1][node2])
    }
}

private fun floyd(n: Int) {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
            }
        }
    }
}