[백준] 1507번 - 궁금한 민호 / 골드 3 / 파이썬 풀이

문제 링크

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

1507번: 궁금한 민호

 

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• 강호와 민호가 N 개의 도시로 이루어진 나라에 살고 있음. (입력으로 주어짐)
• 각 도시는 M 개의 도로로 연결되어 있고, 도로를 지날 때 필요한 시간이 존재함.
  (도로를 지날 때 필요한 시간 => 입력으로 주어짐)
• A->B로 바로 갈 수 있는 도로가 있다 or 다른 도시를 거쳐서 갈 수 있다
  => "도시 A에서 B를 갈 수 있다!"
  
  
• 문제 : 각 도시 간의 최소 이동거리를 알고 있을 때(강호가 구함), 이 나라에 존재할 수 있는 도로의 개수가 최솟값인 경우, 모든 도로의 시간의 합을 구하기.
• EX)
  

  

  예제입력 1 : (1,2) / (2,3) / (1,4) / (3,4) / (4,5) / (3,5) 를 연결하는 도로

  
  

  

  예제입력 4 : (1,3)의 경우 최소경로가 3이 아니라 2가 되어야 맞으므로, 표에 나와있는 경우는 불가능함.

• 종료 조건
  - 강호가 구해놓은 표를 기반으로 도시들을 연결하였을 때, 도시 간의 최소 거리가 강호가 구해놓은 표랑 다를때
    => '불가능'하다고 판단.

 

입력

예제 입력 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

 

예제 입력 2

3
0 2 2
2 0 2
2 2 0

 

예제 입력 3

8
0 1 6 17 26 13 7 16
1 0 5 16 25 12 7 15
6 5 0 21 21 8 12 11
17 16 21 0 41 28 23 31
26 25 21 41 0 13 32 10
13 12 8 28 13 0 19 3
7 7 12 23 32 19 0 22
16 15 11 31 10 3 22 0

 

예제 입력 4

3
0 1 3
1 0 1
3 1 0

 

 

출력

예제 출력 1

55

 

예제 출력 2

6

 

예제 출력 3

69

 

예제 출력 4

-1

---

풀이

 

"플로이드 와샬 알고리즘을 거꾸로 생각해보자!"

import sys

input = sys.stdin.readline

n = int(input())    # 첫째줄에 입력받은 수 = 도시의 개수

s = []
s_ = [[1] * n for i in range(n)]    # 도시 간 간선이 있는지 없는지 판단하기 위한 리스트 (참 or 거짓 => 1 or 0)

result = 0

for i in range(n):
    s.append(list(map(int, input().split())))   # 두번째줄부터 입력받는 강호가 만들어놓은 표


def floyd():
    global result
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j or j == k or i == k:
                    continue
                if s[i][j] == s[i][k] + s[k][j]:
                    s_[i][j] = 0
                elif s[i][j] > s[i][k] + s[k][j]:
                    result = -1     # 강호가 만들어놓은 표 기반의 도시간 최소 거리가 간선을 거쳤을때보다 더 긴 경우


floyd()

if result != -1:        # 강호가 만들어 놓은 표가 불가능한 경우가 아니라면
    for i in range(n):
        for j in range(i, n):   # 숫자표(정사각형) 0(정사각형의 대각선)을 기준으로 나눠진 오른쪽 숫자들만 모두 더함.
            if s_[i][j]:        # 도시 간의 간선이 존재한다면
                result += s[i][j]
print(result)

이미 최단 경로가 입력으로 주어졌으므로, 최단 경로를 구하는 과정인 플로이드 와샬 알고리즘을 역으로 생각하여, 
1. 모든 도시를 간선으로 연결시킨 후,
2. 도시를 거쳐갔을 때(k에 해당)의 비용과 출발 도시(i에 해당)와 도착 도시(j에 해당)간 직접 갔을 때의 비용이 같다면, 해당 출발도시와 도착도시간의 간선은 없애버린다. (간선의 개수가 최소가 되어야 하므로)

3. 도시 간의 간선이 존재하는 경우, 간선 비용을 결과값에 더한다.

 

 

참고

https://mygumi.tistory.com/116

백준 1507번 궁금한 민호 [플로이드] :: 마이구미

https://pacific-ocean.tistory.com/300

[백준] 1507번(python 파이썬)