[백준] 궁금한 민호 (1507)(kotlin)

문제 설명

백준 1507번 문제 링크

입력 및 출력

» 입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 0이 주어지고, 그 외의 경우에 필요한 시간은 2500보다 작거나 같은 자연수이다.

» 출력

첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입출력(테스트케이스)

입력	출력
5 0 6 15 2 6 6 0 9 8 12 15 9 0 16 18 2 8 16 0 4 6 12 18 4 0	55
3 0 2 2 2 0 2 2 2 0	6
8 0 1 6 17 26 13 7 16 1 0 5 16 25 12 7 15 6 5 0 21 21 8 12 11 17 16 21 0 41 28 23 31 26 25 21 41 0 13 32 10 13 12 8 28 13 0 19 3 7 7 12 23 32 19 0 22 16 15 11 31 10 3 22 0	69
3 0 1 3 1 0 1 3 1 0	-1

문제 풀이1

fun main() = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val INF = 987654321
    val dist = Array(N) { IntArray(N) }
    val arr = Array(N) { IntArray(N) }
    val check = Array(N) { BooleanArray(N) }

    repeat(N) {
        val tmp = readLine()
            .split(" ")
            .map { routes -> routes.toInt() }
            .toIntArray()

//        dist[it] = tmp
//        arr[it] = tmp

        for (i in 0 until N) {
            arr[it][i] = tmp[i]
            dist[it][i] = tmp[i]
        }
    }

    for (k in 0 until N) {
        for (i in 0 until N) {
            for (j in 0 until  N) {
                if (i == j || i == k || k == j) continue

                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    println(-1)
                    return
                }

                if (dist[i][j] == dist[i][k] + dist[k][j]) {
                    arr[i][j] = INF
                }
            }
        }
    }

    var answer = 0
    for (i in 0 until N) {
        for (j in 0 until N) {
            if (arr[i][j] != INF && i != j && !check[i][j]) {
                answer += arr[i][j]
                check[i][j] = true
                check[j][i] = true
            }
        }
    }

    println(answer)
}