이 문제를 요약하자면 출발점에서 목적지까지 최단거리를 제외한 그다음 최단거리를 이용한다면 소요되는 비용을 묻는 문제이다. 이 문제를 풀기위한 나의 아이디어는 다익스트라로 우선 최단거리를 구한 후 그 결과를 활용하여 최단거리를 추적하고, 그 최단거리를 삭제한 후에 다시 다익스트라를 이용하여 최단거리를 구하는 것이다. 이를 정리하자면 아래와 같다. 1. 다익스트라를 통해 최단거리를 갈 때 비용을 기록 2. BFS를 활용해서 최단 루트 추적 -> 다익스트라를 기록한 배열을 활용하여 추적함 3. 다익스트라를 다시 하여 최소 비용 구하기 문제를 풀면서 생각한 엣지케이스는 최단거리가 여러 개일 수도 있다는 점이었기 때문에 최단거리를 추적할 때 이를 고려하여 최단 루트를 추적하였다. 이를 코드로 나타내면 아래와같다...
