[🏅5 / 백준 5719 / 파이썬] 거의 최단 경로

 

5719번: 거의 최단 경로

 

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 10⁴)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 10³) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다. 

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

 

예제 입력 7 9 0 6 0 1 1 0 2 1 0 3 2 0 4 3 1 5 2 2 6 4 3 6 2 4 6 4 5 6 1 4 6 0 2 0 1 1 1 2 1 1 3 1 3 2 1 2 0 3 3 0 2 6 8 0 1 0 1 1 0 2 2 0 3 3 2 5 3 3 4 2 4 1 1 5 1 1 3 0 1 0 0

예제 출력 5 -1 6

 

 

풀이

 

개인적으로 굉장히 어려웠던 문제이다.... 쏟은 시간이 수 시간은 되는 것 같다.

어떻게 최단 경로의 간선을 모두 지울 것이냐? 가 이 문제의 관건이다.

 

처음엔 다익스트라를 진행하며 우선순위 큐에 원소를 넣을 때마다 현재까지 지나온 경로를 같이 첨부하는 방식으로 진행했다.

그리고 목표 노드에 도달했다면, 현재까지 지나온 모든 간선을 삭제한다.

최단 경로의 길이가 동일한 경로가 또 있을 수 있으므로, 더 짧은 최단 경로가 나오기 전까진 위의 과정을 반복한다.

그리고 더 짧은 최단 경로가 나왔다면, 다시 처음부터 다익스트라를 진행하여 거의 최단 경로를 찾는 방식이었다.

 

하지만 어떻게 해도 시간초과가 나오거나, 틀린 답이 나오게 되었다.

원인은 최단 경로의 일부를 공유하는 또 다른 최단 경로가 있을 때, 이를 제대로 지우지 못하는 것이었다.

 

 

따라서 다익스트라를 진행한 뒤, 이를 BFS로 역추적하여 최단 경로에 포함되는 간선을 모두 지우는 방식을 택했다.

그리고 마침내 AC를 받을 수 있었다.

 

역추적 방법은 다음과 같다.

끝점부터 해당 노드까지의 거리 + 시작점부터 해당 노드까지의 거리 = 최단 길이 가 나온다면 최단 경로의 간선이다.

이미 다익스트라로 시작점부터 해당 노드까지의 거리는 구했으므로, BFS로 거슬러 올라가며 대조해보면 된다.

 

 

※ 예상 외의 주의할 점

문제에는 거의 최단 경로가 없을 경우도 있다고 했지만, 그냥 최단 경로 자체가 존재하지 않을 수도 있다.

따라서 이 경우에 해당하는 예외 처리가 필요하다.

 

from collections import deque
import sys, heapq
input = sys.stdin.readline

def dijkstra(start,end,edges):
    hq = [(0,start)]
    dist = [float('inf')]*n
    visit = [False]*n
    while hq:
        curDist, curNode = heapq.heappop(hq)
        if visit[curNode]:
            continue
        visit[curNode] = True
            
        if curDist > dist[curNode]:
            continue
        dist[curNode] = curDist
        
        if curNode == end:
            return dist
        for toNode, toDist in edges[curNode]:
            d = curDist + toDist
            if d > dist[toNode] or not edge_check[curNode][toNode]:
                continue
            heapq.heappush(hq,(d,toNode))
            

while True:
    n,m = map(int,input().split())
    if n == 0 and m == 0:
        break
    start, end = map(int,input().split())
    edge = [[] for _ in range(n)]
    edge_reverse = [[] for _ in range(n)]
    edge_check = [[False]*(n) for _ in range(n)]
    
    for i in range(m):
        u,v,p = map(int,input().split())
        edge[u].append((v,p))
        edge_reverse[v].append((u,p))
        edge_check[u][v] = True
    
    dist1 = dijkstra(start,end,edge)
    if dist1 == None:
        print(-1)
        continue
    shortest = dist1[end]
    
    # 최단 경로 제거
    q = deque([(0,end)])
    while q :
        curDist,curNode = q.popleft()
        for toNode,toDist in edge_reverse[curNode]:
            d = curDist + toDist
            if d + dist1[toNode] == shortest:
                if edge_check[toNode][curNode]:
                    edge_check[toNode][curNode] = False
                    q.append((d,toNode))
                
    
    ans = dijkstra(start,end,edge)
    print(ans[end] if ans != None else -1)