1504 - 특정한 최단 경로

이 문제는 1부터 N까지 이동할 때 u, v를 반드시 거치는 최단경로의 거리를 구하는 문제로 다익스트라를 사용하면 풀 수 있다.

이 문제에서 눈여겨봐야 할 곳이 있는데, 다음과 같다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라.

즉 우리가 경로를 찾을 때 간선이나 정점이 중복되는지는 신경 쓸 필요가 없다. 단지 그 경로의 거리가 최소인지만 확인하면 된다.

이제 $dist(a, b)$가 정점 a에서 b까지 최단거리를 주는 함수라고 할 때 $dist(1, N)$은 다음과 같이 구할 수 있다.

$$dist(1, N) = \min \begin{cases} dist(1, u) + dist(u, v) + dist(v, N) \\ dist(1, v) + dist(v, u) + dist(u, N) \end{cases}$$

왜 각 정점에서 정점까지의 최소 거리를 더한 것이 전체의 최소 거리가 될까? 귀류법으로 확인해보자. 어떤 정점으로부터 정점까지의 최소 이동 경로에서 어떤 부분 경로가 최소가 아닐 수 있다고 하자. 그렇다면 그 부분경로가 최소가 아니므로 최소 경로로 갈아끼우면 기존 최소 경로보다 더 작은 전체 최소 경로가 생기는데, 이는 모순이다. 따라서 전체 경로가 최소 비용이면 부분 경로도 최소 비용이다.

🔗 문제 링크

코드

간선이나 탐색 상태를 나타내기 위해 유틸 클래스로 Pair을 선언한다.

static class Pair<T1, T2> {
    public T1 x;
    public T2 y;

    public Pair(T1 x, T2 y) {
        this.x = x;
        this.y = y;
    }
}

정점의 개수 N과 간선의 개수 E를 입력받는다. 다음으로 그래프를 표현할 변수 graph를 선언하고 ArrayList로 초기화한다.

public static void main(String[] args) throws IOException {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N, E;
    N = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());

    @SuppressWarnings("unchecked")
    List<Pair<Integer, Integer>>[] graph = new List[N+1];

    for (int i = 0; i <= N; i++) 
        graph[i] = new ArrayList<>();

그래프를 입력받는다. 문제에서 대칭이라고 하였으므로 from, to 양쪽에 모두 간선을 추가해야 한다. 그런 다음 반드시 거쳐야 하는 정점 u, v를 입력받는다.

    for (int i = 0; i < E; i++) {
        st = new StringTokenizer(br.readLine());
        int from, to, weight;

        from = Integer.parseInt(st.nextToken());
        to = Integer.parseInt(st.nextToken());
        weight = Integer.parseInt(st.nextToken());

        graph[from].add(new Pair<Integer, Integer>(to, weight));
        graph[to].add(new Pair<Integer, Integer>(from, weight));
    }

    st = new StringTokenizer(br.readLine());
    int u, v;
    u = Integer.parseInt(st.nextToken());
    v = Integer.parseInt(st.nextToken());

이제 필요한 다익스트라 연산을 한다. dist1에는 정점 1에서 모든 정점으로의 최단거리가 계산되어 있다. distUV에는 정점 u에서 모든 정점으로의 최단거리가 계산되어 있다. distN에는 정점 N에서 모든 정점으로의 최단 거리가 계산되어 있다.

이 세 가지를 모두 구했다면 답을 계산한다. 이 문제에서 그래프는 무향이므로 $dist(u, v) = dist(v, u)$, $dist(v, N) = dist(N, v)$, $dist(u, N) = dist(N, u)$ 를 이용해 아래 코드와 같이 식을 세울 수 있다.

마지막으로 답을 출력한다. 만약 result가 INF보다 크거나 같다면 1, N까지 갈 수 있는 경로가 없다는 뜻이므로 -1을 출력하고 그렇지 않다면 result를 출력한다.

    long dist1[] = new long[N+1];
    dijkstra(1, dist1, graph);

    long distUV[] = new long[N+1];
    dijkstra(u, distUV, graph);

    long distN[] = new long[N+1];
    dijkstra(N, distN, graph);

    long result = Math.min(
        dist1[u] + distUV[v] + distN[v],
        dist1[v] + distUV[v] + distN[u]
    );

    System.out.println((result >= INF ? -1 : result));
}

다익스트라 함수는 아래와 같다. 일반적인 구현 방법대로 구현했으며 dist를 외부에서 참조형식으로 받아 결과를 넣어준다.

public static void dijkstra(int st, long[] dist, final List<Pair<Integer, Integer>>[] graph) {
    Arrays.fill(dist, INF);
    PriorityQueue<Pair<Integer, Long>> pq = new PriorityQueue<>(Comparator.comparingLong(e->e.y));

    pq.offer(new Pair<Integer, Long>(st, 0L));
    dist[st] = 0;

    while (!pq.isEmpty()) {
        Pair<Integer, Long> s = pq.poll();

        if (s.y > dist[s.x]) continue;

        for (Pair<Integer, Integer> adj : graph[s.x]) {
            if (s.y + adj.y < dist[adj.x]) {
                dist[adj.x] = s.y + adj.y;
                pq.offer(new Pair<Integer, Long>(adj.x, dist[adj.x]));
            }
        }
    }

}

전체 코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Pair<T1, T2> {
        public T1 x;
        public T2 y;

        public Pair(T1 x, T2 y) {
            this.x = x;
            this.y = y;
        }
    }

    static final long INF = Long.MAX_VALUE / 4;
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N, E;
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        @SuppressWarnings("unchecked")
        List<Pair<Integer, Integer>>[] 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 from, to, weight;

            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());

            graph[from].add(new Pair<Integer, Integer>(to, weight));
            graph[to].add(new Pair<Integer, Integer>(from, weight));
        }

        st = new StringTokenizer(br.readLine());
        int u, v;
        u = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        long dist1[] = new long[N+1];
        dijkstra(1, dist1, graph);

        long distUV[] = new long[N+1];
        dijkstra(u, distUV, graph);

        long distN[] = new long[N+1];
        dijkstra(N, distN, graph);

        long result = Math.min(
            dist1[u] + distUV[v] + distN[v],
            dist1[v] + distUV[v] + distN[u]
        );

        System.out.println((result >= INF ? -1 : result));
    }

    public static void dijkstra(int st, long[] dist, final List<Pair<Integer, Integer>>[] graph) {
        Arrays.fill(dist, INF);
        PriorityQueue<Pair<Integer, Long>> pq = new PriorityQueue<>(Comparator.comparingLong(e->e.y));

        pq.offer(new Pair<Integer, Long>(st, 0L));
        dist[st] = 0;

        while (!pq.isEmpty()) {
            Pair<Integer, Long> s = pq.poll();

            if (s.y > dist[s.x]) continue;

            for (Pair<Integer, Integer> adj : graph[s.x]) {
                if (s.y + adj.y < dist[adj.x]) {
                    dist[adj.x] = s.y + adj.y;
                    pq.offer(new Pair<Integer, Long>(adj.x, dist[adj.x]));
                }
            }
        }

    }
} 

시간복잡도

다익스트라의 시간복잡도는 $O((V+E)\log V)$ 로 알려져 있으며 이 문제의 시간복잡도는 $O(3 (N + E) \log N) \approx O((N+E) \log N)$ 이다. 최악의 경우에도 $200800 \times \log 800 \approx 2008000$ 이므로 컴퓨터가 1초에 연산할 수 있는 연산횟수 1억보다 훨씬 작다. 따라서 시간초과 없이 통과 가능하다.