[백준(BOJ)] #1507- 궁금한 민호 (파이썬, PyPy3)

문제

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

1507번: 궁금한 민호

---

문제 풀이

입력으로 모든 도시로 가는 최소 이동 시간이 주어져 이를 역으로 풀어야 합니다. 즉, 플로이드 워셜 알고리즘을 역으로 적용하는 문제입니다.

 

2022.08.01 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘

[파이썬으로 배우는 알고리즘] 플로이드 워셜(Floyd Warshall) 알고리즘

 

만약 주어진 입력에서 도시 c1에서 도시 c2로 가는 시간이 t1이고, 도시 c1, c2로 갈 때 도시 c3를 거쳐가는 시간이 t2일 때, t1이 t2보다 크면 이는 입력이 플로이드 워셜 알고리즘이 성립하지 않음을 의미하기 때문에 불가능한 경우로 -1을 출력합니다.

 

만약 t1과 t2가 같다면,  다른 경로를 통해 연결되어 있다는 뜻으로 직접 연결된 도로는 필요하지 않게 되기 때문에 도로 정보를 지웁니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]
    # 도로 정보 처음엔 다 가능하도록 초기화
    a_check = [[True] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j or j == k or i == k:
                    continue
                # 거쳐가는 시간보다 더 크면 플로이드 워셜 알고리즘 성립 x
                elif a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
                # 직접 연결된 도로 정보 삭제 다른 경로를 통해 이미 연결되어있음
                elif a[i][j] == a[i][k] + a[k][j]:
                    a_check[i][j] = False

    res = 0
    for i in range(N):
        for j in range(i+1, N):
            # 도로 정보가 있는 것만 누적
            if a_check[i][j]:
                res += a[i][j]

    print(res)

 

결과