5719: 거의 최단 경로

문제 링크

5719: 거의 최단 경로

구현 방식

• 전반적인 구현 흐름은 아래와 같다

  • 간선을 입력받을 때, 정방향 간선(edges), 역방향 간선(edges_r), 인접행렬(edges_check)을 완성해준다

    • (경로의 일부를 공유하는 경우를 처리하기 위해 인접행렬을 사용해줌)

  • 먼저 dijkstra를 통해 dists1를 구하고, S부터 D까지의 최단 경로(min_distance = dists1[D])를 구해준다

  • 구해진 dists1을 기반으로, 역방향 bfs 탐색을 수행하여 최단 경로의 간선을 삭제해준다

    • distance + dists1[next] == min_distance을 만족한다면, 최단 경로의 간선임

    • 간선의 삭제는, edges_check[next][curr] = False의 방식으로 수행해줌 (역방향이기 때문에, [next][curr]의 순서가 됨)

  • 이제 최단 경로의 간선을 삭제하였으니, 다시 dijkstra를 수행하여 거의 최단 경로를 구해준다 (dists2)

  • 추가적으로, 아예 최단 경로가 존재하지 않는 경우도 있기에 이 부분을 예외 처리 해주었다

코드

import sys
import heapq
from collections import deque

def dijkstra(S, D):
    global edges, edges_check

    dists = [int(10e9)] * N; dists[S] = 0
    heap = []
    heapq.heappush(heap, [dists[S], S])

    while heap:
        curr_dist, curr = heapq.heappop(heap)
        if dists[curr] < curr_dist: continue

        if curr in edges:
            for next, next_dist in edges[curr]:
                distance = curr_dist + next_dist
                if distance < dists[next] and edges_check[curr][next]:
                    dists[next] = distance
                    heapq.heappush(heap, [distance, next])
    return dists

while True:
    N, M = map(int, sys.stdin.readline()[:-1].split())
    if N == 0 and M == 0: break

    S, D = map(int, sys.stdin.readline()[:-1].split())

    edges = dict()
    edges_r = dict()
    edges_check = [[False]*N for n in range(N)] #경로의 일부를 공유하는 경우를 처리하기 위해 인접행렬 선언

    for m in range(M):
        U, V, P = map(int, sys.stdin.readline()[:-1].split())
        if U in edges: edges[U].append((V, P))
        else: edges[U] = [(V, P)]
        if V in edges_r: edges_r[V].append((U, P))
        else: edges_r[V] = [(U, P)]
        edges_check[U][V] = True

    dists1 = dijkstra(S, D)
    if not dists1: print(-1); continue #최단경로가 존재하지 않는 경우 예외처리
    min_distance = dists1[D]

    # bfs 역추적으로 최단 경로 제거
    queue = deque([]); queue.append((0, D))
    while queue:
        curr_dist, curr = queue.popleft()
        if curr in edges_r:
            for next, next_dist in edges_r[curr]:
                distance = curr_dist + next_dist
                if distance + dists1[next] == min_distance:
                    if edges_check[next][curr]:
                        edges_check[next][curr] = False #최단 경로 제거
                        queue.append((distance, next))

    dists2 = dijkstra(S, D)
    if not dists2: print(-1)
    else:
        if dists2[D] == int(10e9): print(-1)
        else: print(dists2[D])