[BOJ/백준] 5719 거의 최단 경로

import sys
import heapq
 
 
def dijkstra(start,end,flag=True):
    global INF,N
    distance = [INF]*N
    distance[start] = 0
    node_list = []
    heapq.heappush(node_list,(0,start))
    while node_list:
        current_distance,node = heapq.heappop(node_list)
        if current_distance > distance[node]:
            continue          
        for next_node in graph[node]:
            temp_distance = current_distance + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    if flag and distance[end] != INF:
        stack = [(end,distance[end])]
        path_set = set()
        while stack:
            node,dis = stack.pop()
            for prev_node in parent[node]:
                if (prev_node,node) not in path_set:
                    if distance[prev_node] + graph[prev_node][node] == dis:
                        path_set.add((prev_node,node))
                        stack.append((prev_node,distance[prev_node]))
        
        for prev_node,next_node in path_set:
            del graph[prev_node][next_node]
 
    return distance[end]
INF = float('inf')
while True:
    N,M = map(int,sys.stdin.readline().split())
    if not N+M:
        break 
    S,D = map(int,sys.stdin.readline().split())
 
    distance = [[0]*N for _ in range(N)]
    graph = [{} for _ in range(N)]
    parent = [[] for _ in range(N)]
    for _ in range(M):
        U,V,P = map(int,sys.stdin.readline().split())
        graph[U][V] = P
        parent[V].append(U)
    min_distance = dijkstra(S,D)
    if min_distance == INF:
        print(-1)
    else:
        cu_distance = dijkstra(S,D,False)
        if cu_distance != min_distance:
            if cu_distance != INF:
                print(cu_distance)
            else:
                print(-1)

 

 

다익스트라 문제이다. 하지만 기존의 다익스트라와 달리, 최단경로를 찾아서 최적경로의 간선을 제거해줘야한다.

 

처음에, 최적경로 하나마다 삭제를 했더니, 최적경로의 간선은 다른 최적경로에서 사용을 할 수 있기 때문에 틀렸다고 나왔다.

 

두번째로는 시간초과의 늪에 많이 빠졌다. 처음에는 최적의 경로를 min_distance가 갱신될때마다 저장을 시켜놨더니 

 

시간이 초과가 되었다.

 

그래서 다음과 같은 로직으로 최적의 경로쌍을 찾아다

 

도착지점의 distance의 값을 distance[end]라 하겠다.

 

distance[prev_node] + graph[prev_node][end] == distance[end]을 만족하는 prev_node는 prev_node에서 end node로 오는 최단경로임을 알수 있다.

 

이 (prev_node,end) 쌍을 지울 집합에 추가해주고, prev_node를 stack에 넣어준다.

 

이 과정을 반복하면, 끝점에서부터 최단경로로 오는 간선들을 전부 찾을 수 있다.

 

그리고 난뒤 해당 간선들을 지우는 과정을 하면 된다.

 

그리고 마지막으로 다익스트라를 한번 더 한뒤 결과에 맞게 출력해주면 된다.

 

다익스트라는 자주 쓰지 않던 알고리즘이라 푸는데 어려웠고, 기본적으로 다익스트라는 최단경로의 길이를 출력해주는 것이기 때문에, 최단경로의 경로를 이용하기 위해서 다익스트라 과정에서 나온 결과물을 이용해야한다는 점을 배웠다.