[골드 2] 백준 1507 - 궁금한 민호 (파이썬)

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

풀이

모든 도시 쌍 사이 최단 거리가 주어졌을 때, 최소한의 도로만으로도 그 최단 거리 정보를 유지할 수 있는지를 묻고 있다.

• 주어진 거리 행렬은 이미 모든 쌍 최단 거리 정보를 담고 있음 (플로이드 이후 결과)
• 어떤 도로 i-j가 다른 경로 i-k-j에 포함되어 있다면, 굳이 필요하지 않음
• 따라서 직접 연결된 간선 중, 다른 경로로 대체 가능한 간선은 제거

---

주요 변수

• dist[i][j]: 도시 i에서 j까지의 최단 거리
• need[i][j]: i에서 j까지 직접 연결된 간선이 필요한가 여부
• impossible: 삼각 부등식이 깨지는 경우 (즉, 입력이 잘못된 경우)

N = int(input())
dist = [list(map(int, input().split())) for _ in range(N)]
need = [[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:
                continue

모든 i, j, k 쌍을 순회하며 중복/무의미 조합은 스킵한다.

if dist[i][j] + dist[j][k] == dist[i][k]:
    need[i][k] = False

경유지 j를 통해 i가 k를 갈 수 있다면 직접 연결된 간선을 필요없다.

그래서 직접 연결이 아닌 다른 경로로 최단 거리 도달이 가능하므로, 간선을 제거한다.

if dist[i][j] + dist[j][k] < dist[i][k]:
    impossible = True
    break

삼각 부등식 위반이 발생하는 경우 입력 자체가 잘못된것 이므로 -1을 출력한다.

코드

# 백준 1507 - 궁금한 민호
# 분류 : 그래프

N = int(input())
dist = [list(map(int, input().split())) for _ in range(N)]
need = [[True] * N for _ in range(N)]

impossible = False
for i in range(N) :
    for j in range(N) :
        for k in range(N) :
            if i == j or j == k :
                continue

            if dist[i][j] + dist[j][k] == dist[i][k] :
                need[i][k] = False
            
            if dist[i][j] + dist[j][k] < dist[j][k] :
                impossible = True
                break

if impossible :
    print(-1)
else :
    answer = 0
    for i in range(N) :
        for j in range(i + 1, N) :
            if need[i][j] :
                answer += dist[i][j]

print(answer)