[백준] 5719 - 거의 최단 경로

www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

다익스트라 응용문제로 풀게된 문제이다.

solved.ac 기준 플래티넘 5의 난이도를 가진 문제이다.

정말 플레티넘답게 쉽게 안풀리는 문제였다.

질문게시판의 반례와 대회 테스트케이스를 활용해가며 4시간만에 풀었다..

내가 문제에 접근한 방법, 문제를 푼 아이디어를 기록하고자한다.

 

이 문제를 푸는 큰 흐름은 다음과 같다.

다익스트라(최단거리 계산) -> 최단 경로들 삭제 -> 삭제한 경로로 다시 다익스트라

여기에서 이 가운데 최단 경로들을 삭제하는 과정이 여간 까다로웠던게 아니었다.

난 크게 3가지 방법으로 접근을 시도했다.

 

1. (다익스트라 + 경로저장 -> 저장한 경로 삭제) 를

맨 처음 최단 경로값보다 큰 값이 나올 때까지 반복

 

다익스트라를 진행하면서 어느 노드를 거쳐서 최단 경로에 도달했는지 그 경로를 저장한다.

저장한 경로의 각 노드사이 연결된 도로를 모두 제거한다.

그리고 다시 다익스트라를 수행한다.

 

그 결과값이 맨 처음 최단 경로값보다 큰 값이 나올 때까지

반복해서 다익스트라를 수행하고 도로를 제거한다.

 

이 방법은 가볍게 틀렸습니다를 받는다.

맨 처음 구한 최단 경로의 일부를 공유하는 또 다른 최단 경로가 있을 때,

그 또 다른 최단 경로를 지우지 못하기 때문이다.

 

예제 입력처럼 여러개의 최단경로가 있을 때,

각각의 최단 경로가 서로 겹치지 않을 때나 가능한 방법이다.

 

2. 모든 노드를 시작점으로 다익스트라 수행 -> BFS를 돌면서 모든 간선체크

-> 해당 간선이 최단경로에 속하는 간선인지 확인하여 제거 -> 다익스트라

 

이 방법을 개선하려고 떠올린 방법이

모든 노드를 시작점으로 하여 다익스트라를 N번 반복하여 수행하는 것이다.

그러면 N*N 최단경로 배열을 구하게 된다.

그 결과값을 토대로 각각의 간선이 최단 경로에 속한 간선인지 체크한다.

 

예를 들어 시작점이 0이고, 도착점이 4, 기존 최단 경로가 5였다고 하자.

2->3 으로 가는 가중치 2의 간선이 있다고 할 때,

이 도로가 최단 경로에 속한 간선인지 확인 하는 방법은 매우 간단하다

 

0부터 2까지 최단 경로값 + 2에서 3으로 가는 가중치 값 + 3에서 4까지 가는 최단경로값

이렇게 쪼개서 계산한다음, 그 결과값이 기존 최단 경로 값과 같으면 최단경로이다.

 

이걸 모든 "간선"에 대해 반복하기 위해 BFS를 사용했다.

일단 노드에 방문하면 해당 노드로부터 뻗어나가는 모든 간선에 대해 위 방법을 적용하고

각각의 간선에 연결된 노드를 방문하지 않았을 경우 큐에 넣는 식으로 진행했다.

 

그리고 이렇게 풀면 1번 방법에서 발견한 반례를 해결할 수 있게된다.

그리고 제출 결과는 TLE였다.

 

인접리스트를 사용한 다익스트라의 시간복잡도는 O(E log V) 라고 알고 있었다.

다익스트라를 모든 노드에 대해 반복하면 시간복잡도가 O (VE log V) 가 될 것이라고 생각했다.

V <= 500, E <= 10000 이므로

5,000,000 * 2 = 10,000,000 으로 대충 계산해도 1초안에는 가능할 거라고 생각했다.

 

BFS 시간 복잡도는 O( V + E ) 이므로 최대 10,500..

두 과정을 합쳐도 괜찮을 거라고 생각했는데 아니었다.

 

그래서 여기에서 더 나은 방법을 찾기위해 고민하다 3번째 방법을 시도했다.

 

3. 정방향으로 다익스트라, 역방향으로 다익스트라 수행 -> 거꾸로 BFS 수행 -> 다시 다익스트라

 

내가 AC를 받은 방법이다.

사실 모든 노드에 대해 다익스트라를 수행한 이유는

(임의 노드, 도착점 노드) 까지의 거리를 한번에 구하기 위해서였다.

 

A노드와 B노드를 잇는 간선 (A, B)가 최단 경로에 속하는지 보는 방법은

distance(start, A) + distance(A, B) + distance(B, end) == 최단경로

가 성립하면 된다.

 

그렇다면 distance(B, end) 를 구하기 위해 모든 노드에 대해 다익스트라를 수행하는건 비효율적이다.

어차피 끝점이 end인게 확실하다면 거꾸로 end에서부터 역방향으로 최단 경로를 다 구해보면 된다.

 

그래서 처음에 그래프 정보를 저장할 때, 역방향 그래프 정보를 따로 저장하도록 하고,

start를 기준으로 정방향 그래프 따라 다익스트라를 수행하고,

end를 기준으로 역방향 그래프 따라 다익스트라를 수행한다.

 

그리고 BFS를 거꾸로 돌면서 위 공식을 적용하여

모든 간선에 대해 이 간선이 최단 경로에 속한 간선인지 확인한다.

distance(start, A) 는 정방향 다익스트라의 결과로부터

distance(B, end) 는 역방향 다익스트라의 결과로부터 값을 얻을 수 있다.

 

BFS를 도는 방향은 시작점부터 도나 도착점에서 거꾸로 도나 상관은 없다.

어차피 모든 간선을 다 방문해야 하기 때문이다.

단지, 이 아이디어를 떠올릴 때 역방향을 기준으로 생각해서

헷갈리지 않게 BFS도 거꾸로 도는 걸 적용했다.

 

그리고 모든 간선을 다 체크하여 최단 경로에 속한 간선을 없앤다음

다시 정방향 다익스트라를 수행해주면 된다.

 

제출한 코드는 다음과 같다.

문제를 4시간 고민하느라 지친바람에 생각하기 싫어서 그냥 정방향, 역방향 다익스트라 함수를 따로 짰는데,

차이점은 사용한 그래프의 종류밖에 없어서 함수는 하나로 합칠 수 있다.

 

import sys, heapq
from collections import deque
INF = 9876543210


def dijkstra(start):
    pq = []

    dist[start] = 0
    heapq.heappush(pq, (start, dist[start]))
    while pq:
        now_node, distance = heapq.heappop(pq)

        if dist[now_node] < distance:
            continue

        for node, length in graph[now_node]:
            if not available[now_node][node]:
                continue

            if dist[node] > dist[now_node] + length:
                dist[node] = dist[now_node] + length

                heapq.heappush(pq, (node, dist[node]))


def reverse_dijkstra(start):
    reverse_pq = []

    reverse_dist[start] = 0
    heapq.heappush(reverse_pq, (start, reverse_dist[start]))
    while reverse_pq:
        now_node, distance = heapq.heappop(reverse_pq)

        if reverse_dist[now_node] < distance:
            continue

        for node, length in graph_reverse[now_node]:

            if reverse_dist[node] > reverse_dist[now_node] + length:
                reverse_dist[node] = reverse_dist[now_node] + length

                heapq.heappush(reverse_pq, (node, reverse_dist[node]))


while True:
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:
        break

    graph = [[] for _ in range(n)]
    graph_reverse = [[] for _ in range(n)]
    dist =  [INF for _ in range(n)]
    reverse_dist = [INF for _ in range(n)]
    available = [[False for _ in range(n)] for _ in range(n)]
    visit = [False for _ in range(n)]
    q = deque()

    s, d = map(int, sys.stdin.readline().split())
    for _ in range(m):
        u, v, p = map(int, sys.stdin.readline().split())
        graph[u].append((v, p))  # v로 가는데 p의 도로 길이
        graph_reverse[v].append((u, p))
        available[u][v] = True

    # 다익스트라로 최단 경로 구하기
    dijkstra(s)
    reverse_dijkstra(d)

    min_distance = dist[d]

    # 애초에 최단 경로가 존재하지 않을 경우
    if min_distance == INF:
        print(-1)
        continue

    q.append(d)
    visit[s] = True
    while q:
        node_from = q.popleft()
        for node_to, cost in graph_reverse[node_from]:
            if reverse_dist[node_from] + cost == min_distance - dist[node_to]:
                available[node_to][node_from] = False

            if not visit[node_to]:
                q.append(node_to)
                visit[node_to] = True

    dist = [INF for _ in range(n)]
    dist[s] = 0
    dijkstra(s)

    print(-1 if dist[d] == INF else dist[d])