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

import sys

def input():
    return sys.stdin.readline().rstrip()
def floyd():
    result = 0
    for mid in range(N):
        for start in range(N):
            for end in range(N):
                if start == end or end == mid or mid == start or start>end:continue
                if arr[start][end] == arr[start][mid] + arr[mid][end]:
                    if (start,end) in edge_list:
                        edge_list.remove((start,end))
                if arr[start][end] > arr[start][mid] + arr[mid][end]:
                    return -1

    for x,y in edge_list:
        result += arr[x][y]
    return result
N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
edge_list = set()
for i in range(N):
    for j in range(N):
        if i ==j or i>j: continue
        edge_list.add((i,j))

print(floyd())

이 문제는 이해하기 어려웠던 문제였다.

 

이 문제를 읽어 보면 강호는 모든 쌍의 도시에 대해서 최소 이동시간을 구해놓았다고 했다.

 

그리고 민호는 이 표를 보고 원래 도로가 몇개 있는지를 구해보려고 한다고 적혀있다.

 

그러면 예제에 있는 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도,

 

강호가 구한 모든 쌍의 최솟값을 구할수 있다고 했다.

 

이 부분을 통해 유추를 해야한다.

 

원래는 여러 도로가 있었겠지만, 강호는 모든 쌍의 도시에 대해서 최소 이동시간을 구했기 때문에,

 

불 필요한 다른 도로들을 없애버린것이다.

 

즉 1->3 까지의 시간이 15인데 이것은 1->2 와 2->3을 더한 값과 동일하다.

 

1->5 또한 1->4 4->5를 더한 값과 동일하다.

 

즉 A라는 도시에서 B라는 도시를 갈때 A->C + C->B를 만족하는 경우가 있으면, A->B의 도로는 없어도, 동일한 시간 내에 갈 수 있으므로,

 

도로의 개수를 최솟값을 구할때 제외해도 된다.

 

이 부분을 주의해서 문제를 풀어주면 된다.

 

먼저 모든 도로들을 넣어주어야하는데, A->B와 B->A는 동일 하므로,

 

A<B를 만족하는 도로들을 먼저 edge_list에 전부 넣어준다.

 

그러면서 플로이드 와샬을 하면서

 

arr[start][end] == arr[start][mid] + arr[mid][end] 를 만족하는 경우엔, edge_list에서 그 도로를 제외 해준다.

 

또한 우리는 A<B인 경우만 하도록 했으므로, start> end 이거나, start or end 가 mid와 동일할때는 제외하고 검사해준다.

 

그리고 여기서 또 구해야하는 또 다른 경우는 불가능한 경우에 -1을 출력하는 조건이 있다.

 

이 조건을 만족하는 경우는 도시에서 다른 도시까지 가는 시간의 최소값이 갱신 되는 경우이다.

 

갱신 되었을 때에는 -1을 반환해주고, 아닌 경우에는 남은 edge_list를 통해 모든 도로의 시간의 합을 구하면 된다.