[백준/BOJ] 1507번: 궁금한 민호

문제

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

1507번: 궁금한 민호

해설

플로이드 와샬 알고리즘을 역으로 이용하여 문제를 해결할 수 있다.

플로이드 와샬 알고리즘을 생각해보자.

만약 1번 도로, 2번 도로, 3번 도로가 있을 때, 1 - 2, 2 -3번 간 도로가 있다면 1 - 3번 도로는 없어도 1 - 2 -3을 통해 갈 수 있다. 즉 map[1][3] == map[1][2] + map[2][3]이 되는 것이다.

따라서 이 문제에서는 map[1][2] + map[2][3] == map[1][3]이라면, 이 도로는 없어도 되는 도로가 되므로 0으로 저장해준다.

마지막에 남은 도로들의 합을 더한 후, 양방향 도로이므로 / 2를 하여 출력해주면 된다.

코드

import java.util.*

private lateinit var map: Array<IntArray>
private lateinit var road: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    map = Array(n + 1) { IntArray(n + 1) }
    road = Array(n + 1) { IntArray(n + 1) }

    for(i in 1 .. n) {
        val st = StringTokenizer(readLine())
        for(j in 1 .. n) {
            map[i][j] = st.nextToken().toInt()
            road[i][j] = map[i][j]
        }
    }

    if(!reverseFloyd(n)) println(-1)
    else {
        var ans = 0
        for (i in 1..n) {
            for (j in 1..n) {
                ans += road[i][j]
            }
        }

        ans /= 2
        println(ans)
    }
}

private fun reverseFloyd(n: Int): Boolean {
    for(k in 1 .. n) {
        for(i in 1 .. n) {
            for(j in 1 .. n) {
                if(i == k || j == k) continue

                if(map[i][j] > map[i][k] + map[k][j]) return false
                if(map[i][j] == map[i][k] + map[k][j]) road[i][j] = 0
            }
        }
    }

    return true
}