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

문제

• 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다.
  • 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다.
  • 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.
• 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다.
  • 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다.
  • 항상 거의 최단 경로를 찾아준다.
• 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.
• 예를 들어, 도로 지도가 아래와 같을 때를 생각해보자.
  • 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다.
  • 시작점은 S, 도착점은 D로 표시되어 있다.
  • 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)
  • 거의 최단 경로는 점선으로 표시된 경로이다.
  • 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다.
  • 거의 최단 경로는 여러 개 존재할 수도 있다.
  • 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

 

입력

• 입력은 여러 개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ \(10^{4}\))가 주어진다.
  • 장소는 0부터 N - 1번까지 번호가 매겨져 있다.
• 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N)
• 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ \(10^{3}\))
  • 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다.
  • U에서 V로 가는 도로는 최대 한 개이다.
  • 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

 

출력

• 각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다.
• 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

 

 

솔루션

• 다익스트라 -> 최단 경로 제거 -> 다익스트라 형태로 진행하면 된다.
  • 첫 번째 다익스트라 알고리즘으로 최단 경로를 찾는다.
  • 찾은 최단 경로를 제거 한다.
  • 두 번째 다익스트라 알고리즘으로 최단 경로를 찾는다.
    • 이는 최단 경로를 제거한 이후의 최단 경로를 찾는 것이므로 우리가 원하는 거의 최단 경로 (최단 경로에 속하지 않는 경로를 통해 도착지점으로 가는 경로) 인 것이다.
• 최단 경로를 구할 때에는 경로를 역추적 (도착 지점에서부터 시작) 하는 방식으로 구한다.
• 또한, 첫 번째 다익스트라 알고리즘을 수행하고 난 뒤에 리스트에 담기는 노드들이 항상 최단 경로를 이루지는 않는다.
  • 따라서 최단 경로를 제거하는 부분에서 최단 경로인지 확인해줘야 한다 (비용이 최단 경로와 동일한지).

 

Code

• 전체 코드 : Solution_5719

최단 경로를 구하는 다익스트라 알고리즘 함수

public static int Dijkstra(int start, int end) {
    PriorityQueue<Element> pq = new PriorityQueue<>();
 
    cost[start] = 0;
    pq.offer(new Element(start, cost[start]));
 
    while (!pq.isEmpty()) {
        Element cur = pq.poll();
 
        if (cur.value > cost[cur.idx])
            continue;
 
        for (int via = 0; via < N; via++) {
            if (graph[cur.idx][via] != Integer.MAX_VALUE) {
                if (cost[via] >= cost[cur.idx] + graph[cur.idx][via]) {
                    cost[via] = cost[cur.idx] + graph[cur.idx][via];
                    pq.offer(new Element(via, cost[via]));
                    list[via].add(cur.idx);
                }
            }
        }
    }
    
    return cost[end] == Integer.MAX_VALUE ? -1 : cost[end];
}

 

최단 경로를 지우는 함수

public static void DeleteShortestPath(int end) {
    Queue<Integer> queue = new LinkedList<>();
 
    queue.offer(end);
 
    while (!queue.isEmpty()) {
        int cur = queue.poll();
 
        for(Integer pre : list[cur]) {
            if(graph[pre][cur] != Integer.MAX_VALUE && 
                    cost[cur] == (cost[pre] + graph[pre][cur])) {
                queue.offer(pre);
                graph[pre][cur] = Integer.MAX_VALUE;
            }
        }
    }
}

 

결과