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

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

5719번: 거의 최단 경로

클래스 6을 취득했으니 이제 단계별로 풀어보기도 공부해야겠네요

 

 

풀이

P의 값이 여러가지이므로 최단경로를 구하는 알고리즘은 다익스트라를 생각해볼 수 있습니다.

거의 최단 경로는 최단 경로에 포함되는 모든 도로들을 제외한 도로로 이루어진 최단경로입니다.

 

최단 경로에 속하는 모든 도로들을 제외하려면 일단 adj 배열은 2차원 리스트로 하면 도로를 찾는데 O(N), 삭제를 하는데 O(N)이 걸리니, defaultdict와 리스트를 활용하여 도로를 찾는데 평균 O(1), 최대 O(N)이 걸리게 하고, 삭제를 할 때는 삭제대신 해당 경로의 길이 값을 float('inf')로 설정하여 O(1)이 걸리게 만들어주면 시간이 조금 줄어들 수도 있을 것 같습니다.

 

최단 경로의 도로들을 삭제하는 방법을 구했으니 이제 도로들을 찾아야합니다.

도로를 찾는 방법은 숨바꼭질 4 같은 문제에서 만들어봤던 역추적 리스트를 만들어주면 됩니다. 이때 최단 경로가 여러 개일 수도 있으니 2차원 리스트로 만들어서 정점을 여러 개를 저장하게 만들어주면 됩니다.

 

이제 알고리즘 방식은

1. 다익스트라를 돌림. 다 돌렸으면 최단 경로를 구성하는 도로들의 정점이 역추적 리스트에 저장되어 있음

2. 도착지 번호를 큐에 넣고, 큐에 번호를 하나 뽑아 해당하는 정점이 가지고 있는 역추적 리스트에 있는 정점들을 뽑아 경로의 길이를 모두 float('inf')로 바꾸어줌. 그 후 뽑은 정점은 큐에 넣어줌

3. 필요한 변수들을 다시 초기화 시켜주고, 다시 다익스트라를 돌림

4. 다시 다익스트라를 돌렸을 때, 출발지에서 도착지로 갈 수 있으면 숫자값을 출력, 출발지에서 도착지로 갈 수 없으면 -1을 출력

 

 

코드

from heapq import *
from collections import deque, defaultdict as dfd
input = __import__('sys').stdin.readline
 
def dijkstra():
    pq = []
    heappush(pq, [0, s])
    while pq:
        t, x = heappop(pq)
        for nx in adj[x].keys():
            nt = adj[x][nx]
            if visit[nx] == t + nt: vertex[nx].append(x)
            if visit[nx] > t + nt:
                vertex[nx] = [x]
                visit[nx] = t + nt
                heappush(pq, [t + nt, nx])
 
while 1:
    n, m = map(int, input().split())
    if n == m == 0: break
    s, d = map(int, input().split())
    adj = [dfd(lambda : 0) for _ in range(n)]
    vertex = [[] for _ in range(n)]
    visit = [float('inf')] * n; visit[s] = 0
    for i in range(m):
        u, v, p = map(int, input().split())
        adj[u][v] = p
    dijkstra()
    q = deque([d])
    while q:
        x = q.popleft()
        while vertex[x]:
            nx = vertex[x].pop()
            adj[nx][x] = float('inf')
            q.append(nx)
    visit = [float('inf')] * n; visit[s] = 0
    dijkstra()
    print([-1, visit[d]][visit[d] != float('inf')])