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

문제

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

백준 문제집 - 0x1C강 - 플로이드 알고리즘

알고리즘: 그래프 이론, 최단 경로, 플로이드-워셜

---

풀이

 

1. 모든 A-B(B-A)는 연결되어있다.(직접 or 우회)
2. 주어진 간선들은 모두 최단경로 값이다.
3. 단, 갯수는 "최소"가 아니다.

일단 주어진 값들로 A-B 쌍의 거리를 구했을때 최단경로를 만족하는지 확인해야한다. 최소 갯수를 만족하는지는 다음 문제다.
A-B 직행보다 A-K + K-B 우회값이 더 크다면 최단경로가 아닌 셈. (같은 경우는 괜찮다)

첫번째 조건을 만족하지 못했다면 바로 -1를 출력해주고, 만족했다면 다음 단계로 넘어간다.

예제와 함께 보면 이해가 쉽다.

꼭 필요한 도로만 남겨두고 나머지는 제거한다. 남겨둔 도로들의 합이 문제에서 말하는 "모든 도로의 시간의 합"이 되는것이다.

만약 A-B(직행값) == A-K + K-B(우회값)이라면 A-B 도로는 굳이 필요하지 않다. 같은 비용으로 우회해서 갈 수 있기 때문.
따라서 직행값이 우회값보다 적을 경우에만 결과값에 추가한다.

 

전체적인 과정은 다음과 같다.

1. 플로이드 워셜을 수행하며 최단경로를 만족하는지 확인.
   • 갱신은 X
   • A-K + K-B 값이 더 효율적이라면? 주어진 값들이 최단경로가 아닌것이므로 -1를 반환한다.
2. 다시 한 번 플로이드 워셜을 수행하며 최소한의 도로만 남겨둔다.
   • A-B 직행값이 A에서 B로 가는 최단경로일때에만 남겨둠.
   • 전체 결과값의 A-B 도로 비용을 추가.
     • 아니라면 그냥 넘어간다.

 

플로이드 워셜을 "활용"하는 문제라고 할 수 있겠다.

 

전체 코드

"""
1. 최단 경로 그래프인지 확인
2. 아니라면 -1, 맞다면 다음 단계로
3. 플로이드 워셜 수행 -> 최단 거리값 업데이트는 X
4. A - C 도로를 검사할때, A - B - C 값과 A - C 값이 같다면 필요한 도로가 아니인 셈이므로 넘어감.
5. 모든 B를 거친 후 필요한 도로로 판정되면 결과값에 추가
"""

# 메모리: 32412KB / 시간: 40ms
from sys import stdin


input = stdin.readline

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]

# 최단 경로 그래프가 아니라면 -1 반환
def checking():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                # 우회하는 방법이 더 효율적이라면 최단 경로 그래프가 아닌셈
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    return False
    return True


if not checking():
    print(-1)
    exit()

time = 0

for i in range(N):
    for j in range(i+1, N):
        flag = True

        for k in range(N):
            # 경유지가 출발지 or 도착지가 아니고, 우회해서 도착하는 값과 일직선 도로의 값이 같다면
            # => 일직선 도로는 굳이 존재할 필요가 없음
            if k != i and k != j and graph[i][k] + graph[k][j] == graph[i][j]:
                flag = False
                break

        if flag:
            time += graph[i][j]


print(time)

 

사실 최소신장트리(MST)값을 구하면 되지 않나? 싶어서 도전해봤는데 실패했다.
조금 더 생각해보니 당연한 문제였음.
만약 노드 A, B, C, D의 간선이 아래와 같이 구성되어있다고 가정해보자.

A-B = 1
A-D = 2

B-C = 1
C-D = 1

MST를 구하게 되면 (A-B, B-C, C-D) 순으로 이어지겠다. 이 경우 A-D의 값은 3이 된다.
하지만 실제로 A-D의 최단경로는 2이다. 헉!

결론적으론 삽질의 시간이었지만, 막연하게 '이런 문제는 무조건 플로이드 워셜이야~'하는것보단 낫다.