그래프/궁금한 민호

Q·2021년 9월 16일
0

알고리즘/백준

목록 보기
68/70

문제 설명


문제

강호는 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개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간 (≤ 10,000)이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 필요한 시간은 0이다.

출력

첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다. 불가능한 경우에는 -1을 출력한다.


문제링크

전체 코드

import sys

input = sys.stdin.readline
inf = sys.maxsize

n = int(input())

result = 0
dp = [[1]*n for _ in range(n)]
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

for k in range(n): # k 거쳐가는 점
    for i in range(n): # i 시작점
        for j in range(n): # j 끝점
            if i == j or j == k or k == i:
                continue

            if arr[i][j] == arr[i][k] + arr[k][j]:
                dp[i][j] = 0

            elif arr[i][j] > arr[i][k] + arr[k][j]:
                result = -1

if result != -1:
    for i in range(n):
        for j in range(i, n):
            if dp[i][j]:
                result += arr[i][j]

print(result)

해결 방법

플로이드 와샬 알고리즘을 역으로 적용하는 방법

예시)

  • 3번 노드에서 5번 노드로 가는 최단거리의 값이 D, 입력을 받은 배열을 arr라고 가정하자. 임의의 정점 T를 정한다.

  • 현재 3번 노드에서 5번 노드로 가는 최단거리와 3번 노드에서 T를 지나 5번 노드로 가는 거리를 비교한다. D와 arr[3][T] + arr[T][5]를 비교한다는 얘기다.

  • D와 비교대상의 값이 같은 경우 3번 노드와 5번 노드를 직접 연결하는 것보다 돌아가는 게 빠르다는 뜻이다. 그렇다면 3번 노드와 5번 노드를 직접 연결해주는 간선은 없어도 된다는 뜻이다.

  • D가 비교대상의 값 보다 큰 경우는 돌아가는 방법과 직접 연결하는 방법 모두 없는 경우이다. 이럴 경우 -1을 출력하고 알고리즘을 종료하면 된다.

  • D가 비교대상의 값 보다 작은 경우는 현재 T값을 기준으로 돌아가는 것보다 더 최소의 방법이 있다는 뜻 이므로 무시하고 다음 노드에 대해 다시 위의 과정을 수행한다.

출처: https://sungmin-joo.tistory.com/39 [Big-Joo의 공부기록]

profile
Data Engineer

0개의 댓글