백준 - 플로이드(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/11404

 

[문제 설명]

대놓고 플로이드 와샬 알고리즘 문제. 노드의 수도 100개 이하이므로 최악의 경우 시간복잡도가 O(n^3) = 100만이 된다.

공간 복잡도도 O(n^2)이 된다.

[접근 방법]

플로이드 와샬 문제를 풀 때마다 느끼는 거지만, 최댓값을 어떻게 설정해주냐가 중요하다.

단순히 Int.MAX_VALUE로 설정해주면 연산을 통해 오버플로우가 일어나서 음의 값이 되고, 이를 최솟값으로 여겨 오류가 발생한다.

따라서, 오버플로우가 일어나지 않을 정도로 값을 설정해준다.

문제에선 노드의 개수가 100개 가중치는 최대 10만이므로 1000만(100 * 10만)보다 커야 한다.

나는 간선 가중치를 1만으로 잘못봐서 100만으로 제한을 뒀다가 헤멨다.

 

+) 3중 for문 순서를 많이 헷갈렸다.

플로이드 알고리즘은 아래와 같은 순서로 구해야 한다.

a -> b -> c

a -> b -> d

a -> b -> e

 

[내 답안 수정하기]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val map = Array(n) { IntArray(n) { 10000001 } }

    repeat(br.readLine().toInt()) {
        val (start, end, cost) = br.readLine().split(" ").map { it.toInt() }
        map[start - 1][end - 1] = map[start - 1][end - 1].coerceAtMost(cost)
    }
    repeat(n) {
        map[it][it] = 0
    }

    for (k in map.indices) {
        for (i in map.indices) {
            if (i == k) {
                continue
            }
            for (j in map.indices) {
                if (map[i][k] + map[k][j] < map[i][j]) {
                    map[i][j] = map[i][k] + map[k][j]
                }
            }
        }
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    map.forEach {
        it.forEach {
            if (it == 10000001) {
                bw.write("0 ")
            } else {
                bw.write("$it ")
            }
        }
        bw.write("\n")
    }
    bw.flush()
}