✅ 문제

BOJ 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을 출력한다.

💻 코드

import sys
import heapq
from collections import deque
input = sys.stdin.readline
INF = 1e9


def dijkstra():
    q = []
    heapq.heappush(q, (0, start))
    distance = [INF]*(n)
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for v, w in graph[now]:
            if edges[now][v]:
                continue
            cost = dist + w
            if cost < distance[v]:
                distance[v] = cost
                heapq.heappush(q, (cost, v))
    return distance


def bfs():
    q = deque()
    q.append(end)

    while q:
        v = q.popleft()
        if v == start:
            continue
        for node, cost in graphReverse[v]:
            if distance[node] + cost == distance[v] and not edges[node][v]:
                edges[node][v] = True
                q.append(node)


while True:
    n, m = map(int, input().split())
    if not n and not m:
        break
    start, end = map(int, input().split())
    graph = [[] for _ in range(n)]
    graphReverse = [[] for _ in range(n)]
    edges = [[False]*n for _ in range(n)]
    for i in range(m):
        s, e, v = map(int, input().split())
        graph[s].append((e, v))
        graphReverse[e].append((s, v))
    distance = dijkstra()
    bfs()
    distance = dijkstra()
    if distance[end] == INF:
        print(-1)
    else:
        print(distance[end])

🎯 풀이

• 기존의 최단 거리의 루트를 제외하고 최단거리를 구하는 문제이다. 그렇다면 일단 다익스트라로 최단거리를 구해준다.

• 다익스트라를 1회 해준 뒤, BFS를 이용해서 도착지에서 역으로 최단거리와 비교하면서 최단거리로 이동할 때 지나게 되는 경로를 찾아줘서 그 경로를 비활성화 해준다. (True False 저장하는 배열은 따로 생성)

• 그런 뒤에 다시 다익스트라를 해주면 된다. 경로를 비활성화하면서 문제에서 말하는 거의 최단 경로가 안 나올 수도 있으니 마지막에 답을 출력할 때 예외처리해주면 된다.