1. 문제 설명 📌

정점 1 ➜ 정점 N으로 갈 건데, 이 둘 사이에 특정한 정점 A, B를 꼭 거쳐야 한다. 이 특정한 정점 2개를 꼭 거치면서 갈 수 있는 최단 경로의 비용을 구하여라

2. 구현 방법 🗃️

KEY WORD: DIJKSTRA

특정 정점 A,B를 꼭 거치면서, 1 ➜ N 까지 가는 최단 경로는 다음 2가지 중 하나 일 것이다.

1 ➜ A, A ➜ B, B ➜ N 각각의 최단 경로를 구해서 합한다.
1 ➜ B, B ➜ A, A ➜ N 각각의 최단 경로를 구해서 합한다.

이게 가능한 이유는 모든 가중치가 양수이기 때문이다. A,B로 가는 부분적인 최단 경로에서 벗어나는 정점을 방문하는 것 자체가 비용을 늘릴 뿐 도움되지 않는다. 따라서 각각 부분적인 최단 경로의 합이 곧 전체 최단 경로가 될 수 있다. 따라서 1, A, B 각각을 출발점으로 잡고 다익스트라를 진행하여 저기서 제시된 부분적인 최단 경로를 찾는다.

0️⃣ 최단 거리 배열 3개(각각 dist[0], dist[1], dist[2]) 만들기, 인접 리스트 만들기
1️⃣ 1,A,B를 시작점으로 다익스트라를 돌려서 각각의 최단 거리 배열을 완성 시킨다.
2️⃣ 위에서 설명한 최단 경로가 될 수 있는 후보지 2개(이하 ans1, ans2) 를 완성시킨다. (long으로 만든다.)
3️⃣ 만약 후보지의 답이 Integer.MAX_VALUE를 넘는다면, 부분적인 경로 중 최소 한 곳은 그 사이에 경로가 없어서 도달할 수 없다는 뜻이다.
4️⃣만약 후보지 둘 다 Integer.MAX_VALUE를 넘는다면 답으로 -1을 출력한다.
5️⃣아니면 둘 사이의 최단 경로를 출력한다.

(1) 시간복잡도 분석 🕓

정점의 개수를 N, 간선의 개수를 E라고 할 때, 다익스트라 3번 돌려야 함.

$O(3 E \log N)$

3. 코드 소개 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


public class Main {

    static class Node {
        int i;
        int w;

        public Node (int i, int w) {
            this.i = i;
            this.w = w;
        }
    }

    static class Dist {
        int idx;
        int dist;

        public Dist (int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }
    static int N, E, A, B;
    static ArrayList<Node>[] lists;
    static int iter = 0;
    static int [][] dists;
    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        lists = new ArrayList[N + 1];
        dists = new int[3][N + 1];

        for (int i = 1; i <= N; i++) {
            lists[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            lists[start].add(new Node(end, weight));
            lists[end].add(new Node(start, weight));
        }
        st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        // 계산
        dijkstra(1);
        dijkstra(A);
        dijkstra(B);
        long ans1 = (long)dists[0][A] + (long)dists[1][B] + (long)dists[2][N];
        long ans2 = (long)dists[0][B] + (long)dists[2][A] + (long)dists[1][N];
        // 출력
        System.out.println(Math.min(ans1, ans2) >= Integer.MAX_VALUE? -1 : Math.min(ans1,ans2));
    }

    public static void dijkstra(int start) {
        int [] dist = find_dist(start);
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Dist> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.dist));
        dist[start] = 0;
        pq.add(new Dist(start, 0));
        while (!pq.isEmpty()){
            Dist now = pq.poll();
            if(now.dist != dist[now.idx]) continue;
            for (int i = 0; i < lists[now.idx].size(); i++) {
                Node next = lists[now.idx].get(i);
                if(dist[next.i] > dist[now.idx] + next.w) {
                    dist[next.i] = dist[now.idx] + next.w;
                    pq.add(new Dist(next.i, dist[next.i]));
                }
            }
        }
    }
    public static int[] find_dist(int start){
        return dists[iter++];
    }
}

4. 배운 것들 🎯

82%에서 틀렸던 이유✨

A == 1인 경우와 B == N인 경우를 생각하지 못했다. 처음의 find_dist 함수 모양은 다음과 같았다.

    public static int[] find_dist(int start){
        if(start == 1) return dists[0];
        else if (start == A) return dists[1];
        else return dists[2];
    }

이러면 A == 1이었을 때, 이미 계산이 끝난 dist[0]를 초기값으로 생각해서 한번 더 계산을 해버려서 답이 틀어져 버린다.
이를 고치니 해결 되었다.

답 자료형을 `long`으로 바꾸어서 가독성 높이기

위에서 설명했듯이, 사용해야하는 정점들 사이에 간선이 없어서 가지 못하는 경우 Integer.MAX_VALUE가 계산에 더해진다. 이때 ans1이나 ans2의 자료형이 int이면 overflow가 나서 -값으로 바뀌고 결과가 이상해진다. 각 정점들 사이 가중치가 없을 때 마다 if 조건을 걸어 처리하려니, 놓치는 부분도 많았고, 가독성이 떨어졌다.

        // 첫 코드
        int ans0 = -1;
        int ans1 = dists[0][A] + dists[1][B] + dists[2][N];
        int ans2 = dists[0][B] + dists[2][A] + dists[1][N];
        if(1 == A){
            ans0 = dists[1][B] + dists[2][N];
            if(B== N){
            ans0 = dists[0][N];
            }
        }else if (B == N) {
            ans0 = dists[0][A] + dists[1][N];
        }else if (dists[0][A] == Integer.MAX_VALUE || dists[2][N] == Integer.MAX_VALUE){
            ans0 = ans2;
            if(dists[0][B] == Integer.MAX_VALUE || dists[1][N] == Integer.MAX_VALUE) {
                ans0 = -1;
            }
        }else if (dists[0][B] == Integer.MAX_VALUE || dists[1][N] == Integer.MAX_VALUE){
            ans0 = ans1;
        }
        System.out.println(ans0);

이 때문에 틀려서, ans1과 ans2의 자료형을 long으로 바꾸어서 총합이 Integer.MAX_VALUE 보다 높으면 그 사이 최소 하나의 구간은 도달할 수 없음을 알 수 있게 코드를 바꾸어 가독성을 높혔다.

        // 바꾼 후 코드
        long ans1 = (long)dists[0][A] + (long)dists[1][B] + (long)dists[2][N];
        long ans2 = (long)dists[0][B] + (long)dists[2][A] + (long)dists[1][N];
        // 출력
        System.out.println(Math.min(ans1, ans2) >= Integer.MAX_VALUE? -1 : Math.min(ans1,ans2));