[Python 3] BOJ - 5719 "거의 최단 경로"

 # 문제 링크

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

5719번: 거의 최단 경로

 

 # 풀이

 개인적으로 이 문제의 핵심은 다익스트라와 인접 리스트를 역순으로 뒤집는 것이라 생각한다. 시작점에서 출발하여 끝점까지의 최단 경로는 여러 개 존재할 수 있기 때문에 실제 최단 경로를 찾으려 들면 시간초과를 피할 수 없을 것이다. 그런데 최단 경로라는 점을 생각했을 때 최단 경로 상에 있는 간선의 가중치의 합은 곧 끝점의 최단 거리와 같다. 

<그림 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)의 간선이 최단 경로 상의 간선임을 알 수 있다. 이렇게 계속 최단 경로 상의 간선을 탐색하다가 연결된 정점이 시작점이라면 탐색을 종료한다.

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

 

 # 코드

import heapq, sys

# dijkstra1 : 현재 정점 v에서 출발하여 각 정점의 최단거리를 갱신하는 함수
def dijstra1(v):
    d[v] = 0
    q = []
    q.append((0, v))
    while q:
        cur_dist, cur = heapq.heappop(q)
        if d[cur] < cur_dist:
            continue
        for (next, next_dist) in adj[cur]:
            # 다익스트라 갱신 조건을 만족하면서 현재 간선이 최단 경로가 아닌 경우
            if next_dist + cur_dist < d[next] and check[cur][next] == False:
                d[next] = next_dist + cur_dist
                heapq.heappush(q, (next_dist + cur_dist, next))

# dijkstra2 : 현재 정점 v에서 출발하여 최단 경로 간선을 지우는 함수
def dijstra2(v):
    q = []
    q.append((d[v], v))
    while q:
        cur_dist, cur = heapq.heappop(q)
        # 현재점이 시작점이면 탐색 종료
        if cur == s:
            continue
        for (past, past_dist) in rev_adj[cur]:
            # 이미 최단 경로라면 탐색 종료
            if check[past][cur] == True:
                continue
            # 최단 경로 상의 간선인 경우
            if d[past] == d[cur] - past_dist:
                check[past][cur] = True
                heapq.heappush(q, (d[past], past))

INF = 9876543210
while True:
    # 입력부
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:
        break
    s, e = map(int, sys.stdin.readline().split())
    
    # adj : 일반적 인접리스트
    # rev_adj : 방향을 바꾼 역인접리스트
    adj = [[] for _ in range(n)]
    rev_adj = [[] for _ in range(n)]
    # check : (i, j)를 잇는 간선이 최단 경로 상에 있는 간선인지 아닌지 나타내는 2차원 배열
    check = [[False] * n for _ in range(n)]
    
    # d : 시작점에서 출발하여 각 점의 최단거리를 저장하는 배열
    d = [INF] * n
    for i in range(m):
        a, b, c = map(int, sys.stdin.readline().split())
        adj[a].append((b, c))
        rev_adj[b].append((a, c))
    # 첫 다익스트라1로 d 갱신
    dijstra1(s)
    # 이후 다익스트라2로 check 갱신
    dijstra2(e)
    
    # 거리 배열 초기화 후 두번째 다익스트라로 최단 경로 상의 간선을 배제한 최단 경로 갱신
    for i in range(n):
        d[i] = INF
    dijstra1(s)
    
    # 문제의 조건에 따라 정답 출력
    print(d[e] if d[e] != INF else -1)