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

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

1507번: 궁금한 민호

 

import sys
input = sys.stdin.readline


def getSum():
    sum = 0
    isAdded = [[False]*N for _ in range(N)]

    for i in range(N):
        dp = djikstra(i)

        # 불가능한 경우
        if dp == False:
            return -1

        # dp를 돌면서 sum
        for j in range(N):
            dpLength = len(dp[j])

            if dpLength == 0:
                continue

            for k in range(dpLength - 1):
                fr, to = dp[j][k], dp[j][k+1]
                if isAdded[fr][to] == False:
                    sum += graph[fr][to]
                    isAdded[fr][to] = True

            fr, to = dp[j][-1], j
            if isAdded[fr][to] == False:
                sum += graph[fr][to]
                isAdded[fr][to] = True

    return sum//2


def djikstra(start):
    todo = [([start], 0)]
    dp = [[] for _ in range(N)]

    while todo:
        curPath, curDist = todo.pop(0)
        curNode = curPath[-1]

        for n in range(N):
            if n == curNode:
                continue

            nextDist = curDist + graph[curNode][n]
            if nextDist == graph[start][n]:
                todo.append((curPath + [n], nextDist))
                dp[n] = curPath

            # 불가능한 경우
            elif nextDist < graph[start][n]:
                return False

    return dp


if __name__ == '__main__':
    N = int(input())
    graph = [list(map(int, input().split())) for _ in range(N)]

    print(getSum())

 

일반화를 시켜보자면, A에서 B까지 가는 루트(이 때 거리는 같아야함)가 여러 개 있을 때, 가장 긴 루트를 선택해야한다.

모든 노드에 대해 다익스트라를 돌아주는데, 다익스트라의 dp[A]에는, start -> A로의 루트 중에 거리가 같으면서 가장 긴 루트를 담는다. 즉, A에 대해 다익스트라를 1번 돌아주면, A에서 나머지 모든 노드까지의 path를 얻어오는 것이다. 또, 다익스트라 내부에 예외처리를 해주는데, 입력받은 값을 기반으로 형성된 graph보다 더 짧은 루트가 있을 때를 식별해준다.

이렇게 다익스트라를 돌아줬으면, dp의 값을 활용한다. 예시 입력 1의 경우, 모든 노드에 대한 DP는 다음과 같다.

[[], [0], [0, 1], [0], [0, 3]]
[[1], [], [1], [1, 0], [1, 0, 3]]
[[2, 1], [2], [], [2], [2]]
[[3], [3, 0], [3], [], [3]]
[[4, 3], [4, 3, 0], [4], [4], []]

여기서 0에 대한 결과인 [[], [0], [0, 1], [0], [0, 3]]의 [0, 1]의 의미는, "0에서 2까지 방문하려면, 0, 1을 거쳐야한다."이다. 우리는 이러한 지시를 따라서 dp를 돌면서 graph의 값을 sum에 계속해서 추가해준다. 다만 중복이 되지 않게끔 isAdded 리스트를 통해 관리해준다. 우리는 이렇게, 도로 개수가 최소일 때의 모든 방문 경로를 돌아주었다. 다만, 방향성이 없는 그래프인데, isAdded[0][1]과 isAdded[1][0]가 구분이 되지 않으므로 sum값은 2배가 되었을 것이다. 따라서 sum을 2로 나누어주고 리턴해주면 된다.