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

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

1507번: 궁금한 민호

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:20:31

 

---

 

문제 설명

 

 

강호는 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을 출력한다.

 

입력 예시

 

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

 

 

---

 

풀이

 

 

우선 모든 N개의 경로가 연결되어있는 경우를 생각해 보자. (즉 총 경로의 수는 N*(N-1) // 2개이다). 그리고 최단 경로를 보장하기 위해, 경로 i에서 j까지의 시간값은 최소 시간과 동일하다. 이제 우리는 여기서 불필요한 경로를 삭제해 볼 것이다. 불필요한 경로란, 직선 경로를 거치지 않고도 최단 경로로 i에서 j로 갈 수 있는 경우를 의미한다.

 

즉 임의의 k에 대해(k != i, j) road[i][j] == road[i][k] + road[k][j]를 만족한다면 그 경로를 삭제할 수 있다.

 

그렇다면 말이 되지 않는 경우는 무엇일까? 우리는 모든 경로가 최소 시간임을 이미 전제하고 있다. 즉 우회로를 통하였을 때, 최소 시간보다 더 낮은 시간에 도착할 수 있다면 모순이 발생한다. 즉 road[i][j] > road[i][k] + road[k][j]를 만족한다면 모순이 된다.

 

이 두 가지를 모두 한 번에 플로이드-와셜 알고리즘으로 해결해 볼 수 있다. 

 

풀이 코드

import sys
input = sys.stdin.readline

N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]
direct = [[True]*N for _ in range(N)]
for k in range(N) :
  for i in range(N) :
    for j in range(N) :
      if i == j or i == k or k == j :
        continue
      if maps[i][j] > maps[i][k] + maps[k][j] :
        print(-1)
        exit()
      elif maps[i][j] == maps[i][k] + maps[k][j] :
        direct[i][j] = direct[j][i] = False

maps = [[ maps[i][j] if direct[i][j] else 0 for j in range(N)] for i in range(N)]
print(sum(map(sum, maps)) // 2)

풀이 완료!