[백준] 1504번: 특정한 최단 경로 (Java)

문제

링크 : https://www.acmicpc.net/problem/1504

난이도 : 골드4

알고리즘 : 그래프 탐색

---

풀이 과정

간선의 가중치가 각각 다른 무방향 그래프에서 최단 경로를 구해야 하는 문제이다.

다익스트라 알고리즘을 사용하면 얼핏 쉽게 풀릴 것 처럼 보이지만, 특이한 조건이 하나 있다. 문제에서 주어지는 두 정점을 반드시 거치면서 최단 경로로 이동하는 거리를 구해야 한다. 또한 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다.

생각한 방법은 전체 경로를 3개의 경로로 나누는 것이다. 만약 1에서 부터 v1과 v2를 지나 n에 도착해야 한다고 하자. (여기서 v1과 v2의 순서는 무관하다.) 전체 경로를 1에서 v1까지의 최단 경로, v1에서 v2까지의 최단 경로, v2에서 n까지의 최단 경로를 나누어 보자. 각각의 경로에 대해 최단 경로를 구한 뒤에 세 거리의 합이 전체 경로의 최솟값이 될 것이다. 

경로를 세 개로 나누었으니, 다익스트라 알고리즘을 세 번 수행하면 문제를 해결할 수 있어 보였다. 정점과 간선은 재방문해도 상관이 없으므로 다익스트라를 수행할 때 이전 다익스트라에서 방문했는지 여부는 따지지 않아도 된다.

 

구현을 하기 전에 시간복잡도를 계산해보자면, 먼저 다익스트라 알고리즘의 시간복잡도는 O(ElogV)이다. 이 다익스트라 알고리즘을 세 번 수행함으로써 전체 최단 거리를 구하는데,  경로는 1 -> v1 -> v2 -> n 과 1 -> v2 -> v1 -> n 의 두 가지 경우가 있기에 총 6번 다익스트라 알고리즘을 수행한다. 전체 반복횟수는 E log V * 6 = 11572627 < 100,000,000으로 시간 제한에 걸리지 않는다. 

 

두 가지 경로에 대한 최단 경로를 구한 뒤에, 더 짧은 경로의 길이를 출력하면 문제를 해결할 수 있다.

---

코드

import java.io.*;
import java.util.*;

public class Main{
    static int MAX_DISTANCE = 200_000 * 1000 + 1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        List<Edge>[] graph = new List[n+1];
        for(int i=0;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0;i<e;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph[a].add(new Edge(b, c));
            graph[b].add(new Edge(a, c));
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        int sum1 = 0;
        int sum2 = 0;

        int[] distance;
        int[] course1 = {1, v1, v2, n};
        int[] course2 = {1, v2, v1, n};

        for(int i=0;i<3;i++) {
            distance = dijkstra(graph, course1[i]);
            sum1 += distance[course1[i + 1]];

            distance = dijkstra(graph, course2[i]);
            sum2 += distance[course2[i + 1]];
        }

        int answer = Math.min(sum1, sum2);
        if(answer >= MAX_DISTANCE) System.out.print(-1);
        else System.out.print(answer);
    }

    static class Edge{
        int dst;
        int length;

        Edge(int dst, int length){
            this.dst = dst;
            this.length = length;
        }
    }

    static int[] dijkstra(List<Edge>[] graph, int start){
        int[] distance = new int[graph.length];
        Arrays.fill(distance, MAX_DISTANCE);
        distance[start] = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return distance[o1] - distance[o2];
            }
        });

        boolean[] isVisited = new boolean[graph.length];
        isVisited[start] = true;
        pq.add(start);

        while(!pq.isEmpty()){
            int now = pq.poll();
            isVisited[now] = true;
            for(int i=0;i<graph[now].size();i++){
                Edge next = graph[now].get(i);

                if(isVisited[next.dst]) continue;

                if(distance[next.dst] > distance[now] + next.length){
                    distance[next.dst] = distance[now] + next.length;
                    pq.add(next.dst);
                }
            }
        }

        return distance;
    }
}