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

난이도: 플래티넘 5

문제 링크: www.acmicpc.net/problem/5719

5719번: 거의 최단 경로

백준 5719번 문제 거의 최단 경로

 

흔한 최단 경로 문제에 조건이 하나 추가된 문제입니다.

시작점과 끝점이 주어져 있고, 각 노드 간 단방향 거리가 주어졌을 때, 시작점으로부터 끝점까지의 "거의 최단 경로" 를 구하면 됩니다.

여기서 "거의 최단 경로" 란, 최단 경로에 포함되어 있지 않은 경로로만 이루어진 경로를 뜻합니다.

 

제가 고민한 문제 접근 방법은 이렇습니다.

1. Dijkstra 알고리즘을 이용하여 최단 경로를 구한다.

2. 거리가 최단 경로인 경로에 속한 edge(간선)를 모두 제거한다.

3. Dijkstra 알고리즘을 한번 더 이용하여, 남은 경로 중 최단거리를 구한다.

 

1, 3번은 어렵지 않습니다. 알려진 Dijkstra 알고리즘을 그대로 구현하면 됩니다.

문제는 2번인데, 접근을 잘못 하면 시간 초과와 메모리 초과를 경험하게 됩니다.

 

제가 참고한 방법은, trace라는 별도의 배열을 Dijkstra 알고리즘 도중에 함께 갱신하고,

이를 바탕으로 BFS (DFS)를 통해 역으로 접근하는 방법입니다.

 

trace 배열에는 edges 배열과 반대로 key index가 nextNode, output이 currenetNode가 됩니다.

이를 저장한 후, BFS를 통해 trace에 기록된 edge를 지우면 됩니다.

 

 

+ 처음에 작성했다가 결국 해결하지 못한 틀린 코드