백준 - 파티 / Gold 3 / 1238번 / Python

문제 📋

백준 - 파티

풀이 📝

import sys
import heapq
from collections import defaultdict


def dijkstra(start, graph):
    q = []
    distance = [INF] * (n + 1)

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        cur_dist, cur = heapq.heappop(q)

        if distance[cur] < cur_dist:
            continue

        for dest_dist, dest in graph[cur]:
            new_dist = cur_dist + dest_dist

            if new_dist < distance[dest]:
                distance[dest] = new_dist
                heapq.heappush(q, (new_dist, dest))
    return distance


def solution(n, m, x):
    answer = []
    graph_go = defaultdict(list)
    graph_back = defaultdict(list)

    for _ in range(m):
        start, end, t = map(int, sys.stdin.readline().split())
        graph_go[end].append((t, start))
        graph_back[start].append((t, end))

    distance_go = dijkstra(x, graph_go)
    distance_back = dijkstra(x, graph_back)

    for i in range(1, n+1):
        answer.append(distance_go[i] + distance_back[i])

    return max(answer)


INF = int(1e9)
n, m, x = map(int, sys.stdin.readline().split())
print(solution(n, m, x))

최단경로 문제이다.
간선에는 방향과 가중치가 있고 양수이기 때문에 다익스트라 알고리즘을 떠올렸다.
X까지 갔다오는 최단경로를 구해야 했기 때문에
다음과 같이 2가지 경우의 최단경로를 구해야했다.

1. 모든 노드 -> X
2. X -> 모든 노드

다익스트라 알고리즘은 하나의 정점에서부터
모든 정점까지의 최단경로를 구하는 알고리즘이기 때문에
2번 같은 경우엔 쉽게 구할 수 있다.

하지만 1번 같은 경우엔 다익스트라 알고리즘을 모든 노드의 개수인 N번 실행 해야했다.

힙을 사용한 개선된 다익스트라 알고리즘의 시간복잡도는 최악의 경우 O(ElogV)이다.
여기서 V(노드)의 최대개수는 1,000개이고
E(간선)의 최대개수는 10,000 이기 때문에
다익스트라를 V번 실행하면 1,000 10,000 10 = 약 1억 이다.
약 1억 번의 연산일 경우 약 1초 걸리기 때문에 아슬아슬 했다.

따라서 새로운 아이디어를 떠올렸다.
생각해보면 모든 노드 -> X 로의 최단경로를 구할 때
다익스트라를 사용하면 X까지의 최단경로 뿐만 아니라
다른 모든 노드의 최단경로도 다구한다.
즉, 불필요한 정보까지 다 구하기 때문에 비효율적이다.

그럼 X까지의 최단경로만 구하려면 어떻게 해야할까?
바로 그래프 간선의 방향을 뒤집으면 된다.
그래프의 간선을 뒤집고 X -> 모든노드 의 최단경로를 구하면
그것은 사실 X로 가는 최단경로들을 구한 것이다.