[백준 Baekjoon] 1504번 특정한 최단 경로 - JAVA

백준 Baekjoon 1504번 특정한 최단 경로 - JAVA

---

문제 풀이

1 -> v1 -> v2 -> N
1 -> v2 -> v1 -> N

 

위의 두 가지 방법 중에 최단거리로 N까지 가는 방법을 구하는 문제이다. 다익스트라 알고리즘을 사용하여 각 이동(예, 1->v1, v1->v2, 1->v2)의 최단거리를 구하고, 두 가지 방법 중에 최단 경로를 출력하면 된다.

 

각 이동에 대해 다익스트라를 사용하여 총 6번 해도 되지만, 편의상 1, v1, v2에서의 모든 정점과의 최단거리를 구하여 사용하였다.
min[0] = 1에서 모든 정점의 거리
min[1] = v1에서 모든 정점의 거리
min[2] = v2에서 모든 정점의 거리이다.

 

두 방법의 최단경로는 아래의 값을 비교해주어 구한다.
min[0][v1](1 -> v1) + min[1][v1](v1 -> v2) + min[2][N](v2 -> N)
min[0][v2](1 -> v2) + min[2][v1](v2 -> v1) + min[1][N](v1 -> N)

 

경로가 없는 경우가 존재하기 때문에 INF를 2000000000 두고 비교한다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N, E, v1, v2;
    public static List<Node>[] list;

    public static int[][] min;
    public static final int INF = 200000000;

    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());

        list = new List[N + 1];
        min = new int[3][N + 1];

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

        for (int i = 0; i < 3; i++) {
            Arrays.fill(min[i], INF);
        }

        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());

            list[a].add(new Node(b, c));
            list[b].add(new Node(a, c));
        }

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

        min[0][1] = min[1][v1] = min[2][v2] = 0;

        dijkstra(1, 0);
        dijkstra(v1, 1);
        dijkstra(v2, 2);

        int answer = Math.min(
                min[0][v1] + min[1][v2] + min[2][N],
                min[0][v2] + min[2][v1] + min[1][N]
        );

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

    public static void dijkstra(int v, int idx) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visit = new boolean[N + 1];

        pq.offer(new Node(v, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (visit[cur.dest]) continue;
            visit[cur.dest] = true;

            for (Node next : list[cur.dest]) {
                if (min[idx][next.dest] > min[idx][cur.dest] + next.dist) {
                    min[idx][next.dest] = min[idx][cur.dest] + next.dist;

                    pq.offer(new Node(next.dest, min[idx][next.dest]));
                }
            }
        }
    }

    public static class Node implements Comparable<Node> {
        int dest;
        int dist;

        public Node(int dest, int dist) {
            this.dest = dest;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return this.dist - o.dist;
        }
    }

}