[백준] 거의 최단 거리 : 5719 Python

이 문제를 요약하자면 출발점에서 목적지까지 최단거리를 제외한 그다음 최단거리를 이용한다면 소요되는 비용을 묻는 문제이다. 

이 문제를 풀기위한 나의 아이디어는 다익스트라로 우선 최단거리를 구한 후 그 결과를 활용하여 최단거리를 추적하고, 그 최단거리를 삭제한 후에 다시 다익스트라를 이용하여 최단거리를 구하는 것이다.

이를 정리하자면 아래와 같다.
1. 다익스트라를 통해 최단거리를 갈 때 비용을 기록
2. BFS를 활용해서 최단 루트 추적 -> 다익스트라를 기록한 배열을 활용하여 추적함
3. 다익스트라를 다시 하여 최소 비용 구하기

문제를 풀면서 생각한 엣지케이스는 최단거리가 여러 개일 수도 있다는 점이었기 때문에 최단거리를 추적할 때 이를 고려하여 최단 루트를 추적하였다.

이를 코드로 나타내면 아래와같다.

import math
from sys import stdin
from heapq import heappush, heappop
from collections import deque

def dik(S, G, D, R) # 시작점, 목표점, 다익스트라 배열, 활용할 루트
    Q = []
    D[S] = 0
    heappush(Q,[0,S])

    while Q:
        nc, nr = heappop(Q)

        if nr == G:
            return nc

        for c in R[nr]:
            cost = nc + c[1]
            if cost < D[c[0]]:
                D[c[0]] = cost
                heappush(Q,[cost, c[0]])


def bfs(now):
    Q = deque([now])

    while Q:
        n = Q.pop()

        nlen = len(rroute[n])
        # for 문을 순회하면서 삭제하기 위해 반대로 순회함
        for idx in range(nlen-1, -1, -1):
            pre, cost = rroute[n][idx]
            if D[pre] == D[n] - cost:
                Q.append(pre)
                del rroute[n][idx]


input = stdin.readline

while True:
    N, M = map(int,input().split())
    if not (N and M):
        exit()
    S, G = map(int,input().split())

    # 출발점에서 목적지
    route = [[] for _ in range(N)]
    # 목적지에서 출발지
    rroute = [[] for _ in range(N)]

    for _ in range(M):
        p, c, w = map(int,input().split())
        route[p].append([c,w])
        rroute[c].append([p,w])

    D = [math.inf] * N
    dik(S,G,D,route)
    bfs(G)
    D = [math.inf] * N
    dik(G,S,D,rroute)
    print(D[S] if D[S] != math.inf else -1)

BFS를 통해 최단경로를 추적하며 최단경로를 바로 삭제하기 위해 for문을 반대로 돌리며 바로 del을 사용하여 삭제하는 것 말고는 위에서 말한 것과 다른 특별한 아이디어는 없었다.

아직 그래프 탐색 시 DFS / BFS  중 어떤 방법을 사용해야 하는지 확신이 들지 않는다. 꾸준한 연습으로 조금 더 문제 푸는 시간을 단축해야겠다.