[BOJ][Python]1238 풀이

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

1238번: 파티

import heapq
import sys
ssr = sys.stdin.readline

INF = 1000001

def dijkstra(start, edges):
    time = [INF for _ in range(n+1)]
    time[start] = 0
    h = [(0, start)]
    while h:
        cur_time, cur_node = heapq.heappop(h)
        if cur_time > time[cur_node]:
            continue
        for next_time, next_node in edges[cur_node]:
            cost = time[cur_node] + next_time
            if cost < time[next_node]:
                time[next_node] = cost
                heapq.heappush(h, (time[next_node], next_node))
    return time

n, m, x = map(int, ssr().split())
routes = [[] for _ in range(n+1)]
reverse_routes = [[] for _ in range(n+1)]
for _ in range(m):
    departure, arrival, time = map(int, ssr().split())
    routes[departure].append((time, arrival))
    reverse_routes[arrival].append((time, departure))
time_take = [0 for _ in range(n+1)]
time_take = dijkstra(x, routes)
reversed_time_take = dijkstra(x, reverse_routes)
max_time = 0
for i in range(1, n+1):
    max_time = max(max_time, time_take[i]+reversed_time_take[i])
print(max_time)

문제가 어려운 것 보다는 아이디어가 좀 더 중요한 문제라고 생각합니다. 문제에서 시키는대로 할 경우 처음에 각 노드에서 x까지가는 최단 거리를 구하기 위해서 노드의 갯수만큼 데이크스트라를 실행해야하고, 상당히 시간이 걸리게 됩니다. O(mlogn)을 n-1번 반복해야해요. 저도 처음에는 이렇게 풀어서 통과는 했는데 런타임 차이가 많이 나서 보니까 입력받은 그래프를 뒤집는 코드를 다들 사용하셨더라구요. 처음에는 코드를 대충보고 엥 말도 안되지 않나하고 생각했습니다.

 

해당 방법에서의 아이디어는 '기존의 입력을 사용할 때 각 노드에서 x까지가는 최단 거리'가 '간선의 출발점과 도착점을 뒤집어서 사용할 때 x에서 각 노드까지 가는 최단거리'가 같은 결과를 낸다는 부분을 사용한 것입니다. 데이크스트라는 출발점에서 다른 노드에 가는 각각의 최단거리를 알기 용이한 알고리즘이기에 시키는대로 할 경우에 모든 시작노드마다 각각 데이크스트라를 사용해야 하는 것을 한 번으로 가능하게 한 것이죠. 이런 아이디어가 떠올랐다면 그냥 평범한 데이크스트라 2번 반복입니다.

 

데이크스트라에 대해 좀 더 궁금하시다면,

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드