문제 설명

1번 노드에서 N번 노드로 이동을 해야함. 그런데, 중간에 무조건 V1->V2로 가는 길을 포함해야함. 또한, 한 번 이동했던 정점이나 간선도 다시 쓸 수 있다. 이때의 최단 거리는?

문제 제약

노드의 갯수 N은 최대 800개, 간선의 갯수 E는 최대 20만개,
(단, v1 != v2, v1 != N , v2 != 1)

이 문제는 제약조건부터 시작해서 훼이크가 너무많았다고 생각한다;;
v1 과 v2 가 N,1일 수는 없다는 조건은 주고 1,N인 경우는 불가능하다는 말이 없었는데 이걸 캐치하지 못해서 틀린 사람이 많아보였다(사실 나도...).
그리고 내 국어 실력의 문제인지 아니면 문제에서 예시를 안좋은걸 1개만 줘서 그런건지, v1->v2의 간선값만 더해서 틀렸다. 문제에서 예시를 한 개만 줘서 이거라고 생각했는데, 알고보니 v1에서 v2로 가는 경로를 말한거였다.

접근

사실 한 번 이동했던 정점이나 간선에 다시 이동할 수 있다는 거는 별 상관없는 제약이다. 어차피 노드I에서 노드J로 이동하는 최단 경로는 다시 돌아갈 이유가 없기 때문이다.

어차피 우리는 이 문제가 원하는 답을 구하기 위해 다음 두가지 경우 중 한가지로 이동해야 한다.

• 1 -> .. -> v1 -> .. -> v2 -> .. N
• N -> .. -> v2 -> .. -> v1 -> .. 1

즉, 어차피 시키지 않아도 우리는 문제를 다음과 같이 쪼개서 새로운 다익스트라로 시작해야하므로 중복 방문 여부에 대한 불리언배열은 자동으로 초기화된다는 것이다.

다익스트라(1,v1) + 다익스트라(v1,v2) + 다익스트라(v2,N)
or
다익스트라(1,v2) + 다익스트라(v2,v1) + 다익스트라(v1,N)
중 더 짧은 경로를 선택하면 된다.

시간 복잡도는 O(ElogV)를 따라서, 200만 * 6 = 1200만번 연산이므로 널널하다.

그리고 문제 풀때, v1과 v2가 1,N인 경우를 잘 고려해서 알고리즘을 작성해야한다.
나는 이걸 위해 다익스트라 메소드에 start와 end가 같으면 0을 반환하는 로직을 추가했다.
main함수의 N==2일때 반환하도록 만든것은 단지 시간적인 이유 때문이다.

풀이

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

public class Main {
    static int N;
    static int E;
    static int v1;
    static int v2;
    static ArrayList<Node>[] graph;

    static class Node {
        final int number;
        final int cost;

        Node(int number, int cost) {
            this.number = number;
            this.cost = cost;
        }
    }

    static public 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());
        graph = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; 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 Node(b, c));
            graph[b].add(new Node(a, c));
        }

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

        // v1과 v2 사이 길이 없으면 그만해라.
        int v1ToV2 = dijkstra(v1, v2);
        if (v1ToV2 == -1) {
            System.out.println(-1);
            return;
        }
        if (N == 2) {
            System.out.println(v1ToV2);
            return;
        }

        int case1_1toV1 = dijkstra(1, v1);
        int case1_v2toN = dijkstra(v2, N);
        int case1 = case1_1toV1 + v1ToV2 + case1_v2toN;
        if (case1_v2toN == -1 || case1_1toV1 == -1) {
            case1 = -1;
        }

        int case2_1toV2 = dijkstra(1, v2);
        int case2_v1toN = dijkstra(v1, N);
        int case2 = case2_1toV2 + v1ToV2 + case2_v1toN;
        if (case2_v1toN == -1 || case2_1toV2 == -1) {
            case2 = -1;
        }

        if (case1 == -1 && case2 == -1) {
            System.out.println(-1);
        } else if (case1 == -1) {
            System.out.println(case2);
        } else if (case2 == -1) {
            System.out.println(case1);
        } else {
            System.out.println(Math.min(case1, case2));
        }
    }

    static int dijkstra(int start, int end) {
        if (start == end) return 0;
        boolean[] isVisited = new boolean[N + 1];
        int[] dijkstraTable = new int[N + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> {
            return o1.cost - o2.cost; // 최소힙.
        });

        Arrays.fill(dijkstraTable, Integer.MAX_VALUE);
        dijkstraTable[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            if (isVisited[curNode.number]) continue;
            isVisited[curNode.number] = true;
            if (curNode.number == end) {
                return curNode.cost;
            }

            for (Node node : graph[curNode.number]) {
                if (isVisited[node.number]) continue;
                int originCost = dijkstraTable[node.number];
                int newCost = curNode.cost + node.cost;
                if (originCost > newCost) {
                    dijkstraTable[node.number] = newCost;
                    pq.add(new Node(node.number, newCost));
                }
            }
        }

        return -1;
    }
}

느낀점

예시가 1개인 경우 너무 맹신하지 말자.
꺼진 문제제약도 다시 읽자...