백준 1507 궁금한 민호 Kotlin (플로이드 와샬)

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

1507번: 궁금한 민호

문제

강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.

도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.

강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.

예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다. 예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다. 이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수의 최솟값일 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.

입력

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

출력

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

알고리즘 분류

• 그래프 이론
• 플로이드–와샬

풀이

처음 접근은 프림 알고리즘으로 최소 스패닝 트리를 만들고 최단 거리 그래프를 만들고 입력으로 주어진 최단 거리 그래프와 다른 값을 더하는 생쑈를했다.

이 접근의 문제는 최소 스패닝 트리에서 어떠한 간선을 추가해서 입력으로 주어진 최단 거리 그래프와 같게 만들 것인지를 구하기 힘들었다.

결국 풀이를 참고한 결과 그냥 플로이드 와샬의 성질을 이용하면 됐다.

mindis[i][j] == mindis[i][k] + mindis[k][j]이 성립한다면,

i에서 j로 가는 최단 거리 루트가

i에서 k를 거치지 않고 i에서 바로 j로 가는 간선인 dis[i][j],

i에서 k를 거치고 k에서 j로 가는 간선인 dis[i][k] -> dis[k][j]로

두 개의 루트가 있다는 것이다.

이 두 개의 루트에서 버려야 할 것은 무엇일까?

바로 가는 간선인 dis[i][j]이다.

최소한의 간선을 유지하려면 기존에 있는 간선을 최대로 활용하여 i에서 j로 가는 최단 거리를 만드는 것이 유리하기 때문이다.

 

위의 개념을 이용한 풀이는 다음과 같다.

1. 입력으로 주어진 그래프(minDis)를 복사한다.(customMinDis)

2. minDis[i][j] == minDis[i][k]+minDis[k][j]라면 customMinDis[i][j]를 0으로 바꾼다. (i->j 간선을 버린다.)

3. 주어진 그래프는 플로이드 와샬로 구해진 최단 거리 그래프라고 생각해보자. i에서 j로 가는 길이 없는 경우
   minDis[i][j]는 INF가 저장되어 있을 것이다. 즉, minDis[i][j] > minDis[i][k]+minDis[k][j]라면 i에서 j로 가는
   길이 없는 경우로, -1을 출력하고 종료한다.

4. minDis[i][j] < minDis[i][k]+minDis[k][j]라면 무시하면 된다. 이 경우는 가는 길은 있지만 이 길이 최단 경로가 아닌
   경우이다.

5. minDis는 물론 customMinDis도 양방향 간선이다. 단방향 간선만 출력하자. (모든 값을 더한 후 /2를 하든, 반절만
   더하든)

코드

val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()){
    val n = br.readLine().toInt()
    val minDis = Array(n){br.readLine().split(' ').map{it.toInt()}}
    var answer =0
    val customMinDis = Array(n){r->
        IntArray(n){c->
            minDis[r][c]
        }
    }
    for(k in 0 until n){
        for(i in 0 until n){
            for(j in 0 until n){
                if(i==k || k==j) continue
                if(minDis[i][j]==minDis[i][k]+minDis[k][j]){
                    customMinDis[i][j]=0
                }
                else if(minDis[i][j] > minDis[i][k]+minDis[k][j]){
                    write("-1")
                    close()
                    return
                }
            }
        }
    }
    for(i in 0 until n-1 ){
        for(j in i+1 until n){
            answer+=customMinDis[i][j]
        }
    }
    write("$answer")
    close()
}