[백준/BOJ] 11404번: 플로이드

문제

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

11404번: 플로이드

해설

문제의 이름에서부터 알 수 있듯이 플로이드 와샬 알고리즘을 사용하면 된다.

n의 범위가 (2 ≤ n ≤ 100)이고, m의 범위가 (1 ≤ m ≤ 100,000)이기 때문에 각 노드 사이의 비용 초기값을 10,000,000으로 설정하였다.

이 문제에서 주의할 점은 다음과 같다.

• 시작 도시와 도착 도시가 같은 경우는 없다.
• 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
• i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

초기값을 설정해준 후, 시작 도시와 도착 도시가 같다면 0으로 설정해준다.

또한 시작 도시와 도착 도시를 연결하는 노선은 가장 작은 값으로 저장해주면 된다.

플로이드 와샬 알고리즘을 전부 마치고 i에서 j로 가는 비용이 초기값인 10,000,000과 같다면 i에서 j로 갈 수 없는 경우이다. 따라서 0을 출력해주면 된다.

코드

private lateinit var minCost: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()) {
    val cityCnt = readLine().toInt()
    val busCnt = readLine().toInt()

    minCost = Array(cityCnt + 1) { IntArray(cityCnt + 1) { 10000000 } }

    for(i in 1 .. cityCnt) minCost[i][i] = 0

    repeat(busCnt) {
        val (start, end, cost) = readLine().split(" ").map { it.toInt() }
        if(minCost[start][end] > cost) minCost[start][end] = cost
    }

    floydWarshall(cityCnt)
}

private fun floydWarshall(n: Int) {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                if(minCost[i][k] + minCost[k][j] < minCost[i][j]) {
                    minCost[i][j] = minCost[i][k] + minCost[k][j]
                }
            }
        }
    }

    for(i in 1 .. n) {
        for(j in 1 .. n) {
            if(minCost[i][j] == 10000000) print("0 ")
            else print("${minCost[i][j]} ")
        }
        println()
    }
}