[백준] 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 = int(1e9)

def dijkstra(start):
    dist =[INF] * (n)

    dist[start] = 0
    q = []
    heapq.heappush(q,(0,start))
    while q:
        distance, now = heapq.heappop(q)
        if dist[now] < distance:
            continue
        for i in array[now]:
            if edges[now][i[0]]: continue
            cost =  distance + i[1]
            if dist[i[0]] > cost:
                dist[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))
    return dist

def bfs():
    q = deque()
    q.append(d)
    
    while q:
        current = q.popleft()

        if current == s:
            continue
        for node, cost in array_inv[current]:
            if dist[node] + cost == dist[current] and not edges[node][current]:
                edges[node][current] = True
                q.append(node)

result = []
while 1:
    n,m = map(int,input().split())

    if not (n and m):
        break
    s,d = map(int,input().split())

    array =[[] for _ in range(n)]
    array_inv =[[] for _ in range(n)]
    edges = [ [False]*(n+1) for _ in range(n+1)]
    for _ in range(m):
        u,v,p = map(int,input().split())
        array[u].append([v,p])
        array_inv[v].append([u,p])

    dist = dijkstra(s)
    bfs()
    dist = dijkstra(s)
    result.append(-1 if dist[d] == INF else dist[d])

for a in result:
    print(a)

후기

• 솔직히 해당 문제는 풀이를 보면서 풀은 문제이기도 하고, bfs를 오랜만에 풀어봤더니 알고리즘이 잘 생각나지 않아 잘 풀지 못했던 문제이다.
  BFS에 다시 익숙해지고 나서 풀어야 겠다.