[백준] 5718번 : 거의 최단 경로

5719번: 거의 최단 경로

5719번: 거의 최단 경로

🤔 문제분석

어제와 오늘 이 문제 때문에 머리가 너무 아팠습니다 😂

이틀동안 고민해봤지만, 시간초과와 메모리초과를 해결할 수 없어, 해결방안을 찾아보았습니다.

우선, 데이트스트라로 문제를 풀어야 했다는걸 알았지만, 데이크스트라의 최단경로를 어떻게 백트래킹 할 수 있을까 생각해 보았지만, 좋은 아이디어가 떠올리지 않았습니다.

 

문제의 핵심은 데이크스트라, 너비우선탐색으로 해결 할 수 있습니다.

 

문제의 포인트는, 데이크스트라로 최단경로를 갱신한뒤 너비우선탐색으로 기존 경로를 역추적하고, 역추적한 간선을 모두 제거(최단경로 제거)합니다.

 

데이크스트라로 최단경로를 구합니다. 여기서 구한 최단경로의 길이와 역방향의 간선을 정보를 가지고 역 추적이 가능합니다.

역추적을 할때에는 소스의 최단경로거리 - 역방향 간선의 길이 = 타깃의 최단경로의 거리와 일치해야 최단경로 입니다.

따라서 추가로 필요한 자료구조는 역방향의 간선의 정보입니다.

 

새롭게 갱신된 간선으로 데이크스트라로 최단경로를 구한다면 문제를 해결 할 수 있습니다.

📝 의사코드

1. 데이크스트라를 통해 최단경로를 구한다.
2. 너비우선탐색을 통하여 최단경로를 역추적한다.
   1. 첫 출발을 목적지로 하여 출발한다.
   2. 역방향의 간선을 정보를 가지고 노드를 방문해갑니다.
      1. 최단경로라면 큐에 추가합니다. ( 소스최단거리 - 간선의 길이 == 타깃최단거리 )
3. 모든 최단경로를 제거한다.
4. 데이크스트라를 통해 최단경로를 재갱신한다.

💻 코드

import sys
import heapq
from collections import deque

input = sys.stdin.readline

INF = int(1e9) + 1

def disikstra():
    queue = []
    heapq.heappush(queue, (0 , S))
    distance[S] = 0
    
    while queue:
        dis, node = heapq.heappop(queue)
        
        if dis > distance[node]:
            continue
        
        for next_node in edge[node]:
            new_dis = cost[(node, next_node)] + dis
            if distance[next_node] > new_dis:
                distance[next_node] = new_dis
                heapq.heappush(queue, (new_dis, next_node))

def bfs():
    queue = deque([D])
    remove_node = list()
    while queue:
        node = queue.popleft()
        
        for next_node in r_edge[node]:
            if distance[next_node] == distance[node] - cost[(next_node, node)]:
                if (next_node, node) not in remove_node:
                    queue.append(next_node)
                    remove_node.append((next_node, node))

    return remove_node

while True:
    N, M = map(int, input().split())
    if N + M == 0:
        break
    
    S, D = map(int, input().split())
    edge = [set() for _ in range(N)]
    r_edge = [set() for _ in range(N)]
    cost = {}
    
    for _ in range(M):
        U, V, P = map(int, input().split())
        edge[U].add(V)
        r_edge[V].add(U)
        cost[(U, V)] = P
    
    distance = [INF for _ in range(N)]
    disikstra()
    remove_node = bfs()
    for cur, next in remove_node:
        edge[cur].discard(next)
    
    distance = [INF for _ in range(N)]
    disikstra()
    if distance[D] == INF:
        print(-1)
    else:
        print(distance[D])

🎯 피드백 및 개선사항

데이크스트라를 역 추적 할 수 있는 방법을 알게되었고, 데이크스트라 알고리즘이 어떻게 동작되는지 다시한번더 생각해보는 시간이 되었습니다. 문제를 해결하는데에 긴 시간이 걸렸지만 많은 시행착오를 겪음으로, 다음에 데이크스트라 문제를 풀때에는 자신감이 생겼습니다.