[ 백준 ][ 골드3 ] 1238번 - 파티 ( 파이썬 PYTHON )

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

1238번: 파티

 

코드

---

import sys
input = sys.stdin.readline

import heapq
def dijkstra(start):
    Q = []
    heapq.heappush(Q,(0,start))
    dist = [1e9] * (n + 1)
    dist[start] = 0
    while Q:
        total, node = heapq.heappop(Q)
        if dist[node] < total:
            continue
        for time,next_node in edges[node]:
            s = total + time
            if dist[next_node] > s:
                dist[next_node] = s
                heapq.heappush(Q,(s,next_node))
    return dist


n,m,x = map(int,input().split())
edges = [[] for _ in range(n+1)]

for _ in range(m):
    a,b,t = map(int,input().split())
    edges[a].append([t,b])

ans = 0
back = dijkstra(x)
for i in range(1,n+1):
    go = dijkstra(i)
    ans = max(back[i] + go[x], ans)

print(ans)

 

풀이

---

처음에는 각 마을에서 X마을까지의 최단거리와  X마을에서 각 마을까지의 최단거리를 모두 구해야 한다는 생각에 플로이드-워샬 알고리즘을 사용했다. 하지만 플로이드-워샬을 사용하기에는 O(n^3)이기 때문에 시간초과가 발생했다.

 

X마을에서 각 마을까지의 최단거리는 한 번의 다익스트라로 가능하기 때문에 한 번만  수행하고 각 마을마다 다익스르타를 수행해서 X마을까지의 최단거리를 구했다.

 

하지만 시간복잡도가 랭킹에는 56ms이고 내 코드는 1000ms으로 20배가까이 차이가 났다.

 

이 차이점을 알기 위해서 랭킹3등의 코드를 살펴보니 각 마을에서 X마을까지의 최단거리를 구하는 방식이 달랐다.

각 마을에서 X마을까지의 최단거리를 각 마을마다 다익스트라를 수행하지 않고 단 한 번의 다익스트라로 구할 수 있었다.

• 단방향 간선 정보를 역방향으로 한번 더 저장한다.
• 역방향으로 정렬된 그래프에서 X를 시작점으로 다익스트라를 수행한다.
• 여기에 연결된 모든 점들은 X와 최단거리이다 -> 다시말하자면 모든 점들에서 X로 향하는 최단거리가 된다.