[백준] 1504번 : 특정한 최단 경로 - 자바[Java]

1504번: 특정한 최단 경로

풀이

최단 경로를 구하는 문제지만, 특정 정점을 지나는 최단 경로의 길이를 구해야 한다.

1번 정점 -> N번 정점의 최단 경로를 구해야 하는데, 두 정점 v1, v2를 거치는 최단 경로를 구해야 한다.

 

즉 위 조건을 만족하는 1번 정점 -> N번 정점의 최단 경로는 두가지가 있다.

1. 1 -> v1 -> v2 -> N
2. 1 -> v2 -> v1 -> N

그렇다면 각 정점부터 정점까지의 최단 경로를 구해서, 모든 최단 경로의 길이를 더한 1번 정점 -> N번 정점의 최단 경로를 구한다.

그 다음 두 경로 중 최솟값을 출력한다.

 

주의할 점

각 정점부터 정점까지의 최단 경로를 구할 때, 최단 경로가 존재하지 않는다면(최단 경로 값이 Integer.MAX_VALUE), 해당 경로는 불가능한 경로다. 즉, 1번 정점 -> N번 정점으로 가는 두 가지의 최단 경로 모두 불가능한 경로라면  -1을 출력해야 한다.

코드

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

public class Main {

    static class Edge implements Comparable<Edge>{
        public int vertex;
        public int cost;

        Edge(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }
        @Override
        public int compareTo(Edge ob){
            return this.cost - ob.cost;
        }
    }

    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 m = Integer.parseInt(st.nextToken());

        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());

        for (int i = 0; i < m; 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.get(a).add(new Edge(b, c));
            graph.get(b).add(new Edge(a, c));
        }
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        int[][] minDistance = new int[2][3];
        int[] dis;

        dis = dijkstra(graph, n, 1);
        minDistance[0][0] = dis[v1];    //1 -> v1
        minDistance[1][0] = dis[v2];    //1 -> v2

        dis = dijkstra(graph, n, v1);
        minDistance[0][1] = dis[v2];    //v1 -> v2
        minDistance[1][1] = dis[n];     //v1 -> n

        dis = dijkstra(graph, n, v2);
        minDistance[0][2] = dis[n];     //v2 -> n
        minDistance[1][2] = dis[v1];    //v2 -> v1

        int path1 = getPath(minDistance, 0);
        int path2 = getPath(minDistance, 1);

        if (path1 == Integer.MAX_VALUE && path2 == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(Math.min(path1, path2));
    }

    private static int getPath(int[][] minDistance, int row) {
        int path = 0;
        for (int i = 0; i < 3; i++) {
            if (minDistance[row][i] == Integer.MAX_VALUE) {
                path = Integer.MAX_VALUE;
                break;
            }
            path += minDistance[row][i];
        }

        return path;
    }

    static int[] dijkstra(ArrayList<ArrayList<Edge>> graph, int n, int start) {
        int[] dis = new int[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[start] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int vertex = cur.vertex;
            int cost = cur.cost;

            if (dis[vertex] < cost) continue;

            for (Edge e : graph.get(vertex)) {
                if (dis[e.vertex] > cost + e.cost) {
                    dis[e.vertex] = cost + e.cost;
                    pq.add(new Edge(e.vertex, dis[e.vertex]));
                }
            }
        }

        return dis;
    }

}