백준 5719번 거의 최단 경로

문제

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

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

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

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

입력

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

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

출력

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

 

2. 코드

import sys
from heapq import heappop, heappush

INF = sys.maxsize
input = sys.stdin.readline

def dijstra(start):
    dis[start] = 0
    queue = []
    heappush(queue, (0, start))

    while queue:
        dist, now = heappop(queue)

        if dis[now] < dist:
            continue

        for i in maps[now]:
            cost = dist + i[1]
            if cost < dis[i[0]] and not check[now][i[0]]:
                dis[i[0]] = cost
                heappush(queue, (cost, i[0]))
def dijstra2(start):
    queue = []
    heappush(queue, (dis[start], start))

    while queue:
        dist, now = heappop(queue)

        if now == s:
            continue

        for i in reverse_maps[now]:
            if check[i[0]][now]:
                continue
            if dis[i[0]] == dis[now] - i[1]:
                check[i[0]][now] = True
                heappush(queue, (dis[i[0]], i[0]))
while True:
    n, m = map(int, input().split())
    if not n and not m:
        break
    s, e = map(int, input().split())

    maps = [[] for _ in range(n)]
    reverse_maps = [[] for _ in range(n)]

    check = [[False] * n for _ in range(n)]
    dis = [INF] * n
    for _ in range(m):
        u, v, p = map(int, input().split())
        maps[u].append((v, p))
        reverse_maps[v].append((u, p))
    dijstra(s)
    dijstra2(e)

    for i in range(n):
        dis[i] = INF
    dijstra(s)
    if dis[e] == INF:
        print(-1)
    else:
        print(dis[e])

 

3. 풀이

1. 시작점 다익스트라 와 도착점 다익스트라의 가중치 합이 동일 하다는 점을 이용한다.

ex)

<그림 1. 예제 1의 첫번째 TC>

 위 그림 1에서는 원래 인접 리스트의 방향이 반대인 역인접 리스트와 시작점에서 출발하여 각 점까지의 최단 거리 배열을 나타내고 있다. 이 때 임의의 한 점과 연결된 간선들 중에서 최단 경로 상의 간선을 찾는 방법은 임의의 한 점과 간선으로 연결된 정점의 최단거리에서 현재점까지의 거리의 차이가 간선의 길이와 일치 여부로 알 수 있다. 

 예를 들어 위 그림 1에서 현재점이 6이라고 하자. 따라서, 6과 연결된 정점들은 2,3,4,5이다. 그런데 (2, 6)의 간선의 경우는 만약에 이 간선이 정말로 최단 경로 상의 간선이었다면 현재 D[2]에서 간선의 가중치인 4를 더한 5가 D[6]과 같아야 한다. 그런데 그렇지 않으므로 (2, 6)의 간선은 절대로 최단 경로 상의 간선이 될 수 없음은 자명하다. 이 논리에 의해 (3, 6), (5, 6)의 간선이 최단 경로 상의 간선임을 알 수 있다. 이렇게 계속 최단 경로 상의 간선을 탐색하다가 연결된 정점이 시작점이라면 탐색을 종료한다.

 위 작업이 끝나고 나면 최단 경로 상의 간선을 모두 지울 수 있고 지워진 간선들로 시작점에서 끝점까지의 최단 경로를 문제의 요구에 맞게 출력하면 정답을 구할 수 있다.