[Python] BOJ / 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을 출력한다.

풀이

플로이드 와샬 알고리즘을 이미 적용시킨 그래프를 주어주는 문제로 모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때, 이 나라에 존재할 수 있는 도로의 개수가 최솟값일 때, 모든 도로의 시간의 합을 구하는 문제이다.

 

도로의 존재 여부를 저장하기 위한 2차원 배열을 따로 만들어놓고

1. 도시 i -> j로 가는 시간이 도시 i -> k + k -> j로 가는 시간과 같다면 다른 도시를 거쳐서 왔다는 뜻이므로 i -> j를 False로 설정해준다.
2. 도시 i -> j로 가는 시간이 도시 i -> k + k -> j로 가는 시간보다 크다면 시간이 잘못 입력되었다는 뜻이므로 -1을 출력한다.
3. 2번의 경우가 아니라면 road 배열의 값이 True인 경우의 두 도시 사이 도로의 시간을 출력값에 더해준다.

위의 모든 과정은 i != j, i != k, j != k일 때 성립한다.

도시 i -> i로 가는 시간은 0이므로 위의 1번 과정에서 모든 i -> j가 False가 되기 때문이다.

---

import sys

input = sys.stdin.readline

def floyd():
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j or i == k or j == k:
                    continue
                if time[i][j] == time[i][k] + time[k][j]:
                    road[i][j] = False
                elif time[i][j] > time[i][k] + time[k][j]:
                    print(-1)
                    exit(0)

n = int(input())
time = [list(map(int, input().split())) for _ in range(n)]  # 도로의 시간
road = [[True] * n for _ in range(n)]   # 도로 존재 여부

floyd()

ans = 0
for i in range(n):
    for j in range(i, n):
        if road[i][j]:  # 도로가 존재할 경우
            ans += time[i][j]
print(ans)