[Python] 백준 1238번: 파티

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

1238번: 파티

 

import sys
input = sys.stdin.readline
INF = 100*1000+1


def dijkstra(start, graph):
    dp = [INF]*(N+1)
    dp[start] = 0
    todo = [(start, 0)]

    while todo:
        curNode, curTime = todo.pop(0)

        if curTime > dp[curNode]:
            continue

        for e, t in graph[curNode]:
            nextTime = curTime + t

            if nextTime < dp[e]:
                dp[e] = nextTime
                todo.append((e, nextTime))

    return dp


if __name__ == '__main__':
    # 입력
    N, M, X = map(int, input().split())

    g1 = [[] for _ in range(N+1)]
    g2 = [[] for _ in range(N+1)]

    for _ in range(M):
        s, e, t = map(int, input().split())
        g1[s].append((e, t))
        g2[e].append((s, t))

    # 다익스트라
    dp1 = dijkstra(X, g1)
    dp2 = dijkstra(X, g2)

    # 출력
    maxTime = max([dp1[i] + dp2[i] for i in range(1, N+1)])
    print(maxTime)

 

다익스트라는 특정 지점으로부터 모든 곳까지의 최소 거리를 알아낸다. 이 문제의 예제 입력 1의 경우에는, (모든 노드->2)의 최단 거리와 (2->모든 노드)의 최단거리가 필요하다. 여기서 (2->모든 노드)는 다익스트라를 통해 쉽게 얻을 수 있다. 그럼 (모든 노드->2)의 최단 거리는 어떻게 구해야하는가? 바로, 그래프의 방향을 뒤집으면 된다.

 

아래 사진은 예제 입력 1의 그래프이다.

여기에서 2부터 시작하는 다익스트라 알고리즘을 이용하면, (2->모든 노드)의 최단거리를 구할 수 있다.

 

이것의 방향을 뒤집으면 아래처럼 된다.

여기서 또 다시, 2부터 다익스트라를 시작해주면, (모든 노드->2)를 얻을 수 있다. 2번의 다익스트라를 통해 얻은 dp는 다음과 같다.

[INF, 1, 0, 3, 7]

[INF, 4, 0, 6, 3]

 

마지막으로, (1+4), (0+0), (3+6), (7+3) 중에서 최대값을 찾고, 이를 출력해주면 된다.