[백준] 1504번 : 특정한 최단 경로

1504번: 특정한 최단 경로

# 문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

# 입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

# 출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

# 예제 입력 1

4 6

1 2 3

2 3 3

3 4 1

1 3 5

2 4 5

1 4 4

2 3

# 예제 출력 1

7

---

[다익스트라 알고리즘 + DP]

기본적인 다익스트라 문제에서 조금 변형된 문제이다. 1번 정점에서 N번 정점으로 가는 최단 경로가 아닌, 특정 정점 v1, v2를 반드시 거쳐서 정점 N으로 가는 최단 경로를 구한다. 가장 쉬운 방법은,

 

1번 정점 -> v1 정점 -> v2 정점 -> N번 정점

1번 정점 -> v2 정점 -> v1 정점 -> N번 정점

중에 더 작은 값을 구하면 된다.

 

i번 정점에서 다른 정점들로 가는 최단 경로를 저장한 배열을 distance[i][]라고 할 때,

 

distance[1][v1] + distance[v1][v2] + distance[v2][N]

distance[1][v2] + distance[v2][v1] + distance[v1][N]

중 더 작은 값을 출력하도록 한다.

 

단, 모든 정점에 대하여 Dijkstra 알고리즘을 수행할 필요는 없으므로 시작 정점인 1번 정점과 v1 정점, v2 정점에 대하여 다익스트라 함수를 실행하도록 한다.

# Code </>

public class Main {

    static class Edge implements Comparable<Edge>{
        int target, dist;
        public Edge(int t, int d){
            target = t;
            dist = d;
        }
        @Override
        public int compareTo(Edge o) {
            return dist - o.dist;
        }
    }
    static final int INF = 1000000000;
    static int v, e, v1, v2;
    static Queue<Edge> Q = new PriorityQueue<>();
    static List<Edge>[] list;
    static int[][] distance;

    static void Dijkstra(int start){

        distance[start][start] = 0;
        Q.add(new Edge(start, 0));

        while(!Q.isEmpty()){
            Edge edge = Q.poll();
            int current = edge.target;
            int dist = edge.dist;

            if(distance[start][current] < dist) continue;

            for(int i=0; i<list[current].size(); i++){
                Edge edge_ = list[current].get(i);

                int next = edge_.target;
                int nextDist = dist + edge_.dist;
                if(distance[start][next] > nextDist){
                    distance[start][next] = nextDist;
                    Q.add(new Edge(next, nextDist));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        list = new ArrayList[v+1];
        distance = new int[v+1][v+1];

        for(int i=1; i<=v; i++)
            list[i] = new ArrayList<>();

        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine());

            int home = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());

            list[home].add(new Edge(target, dist));
            list[target].add(new Edge(home, dist));
        }

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

        for(int i=1; i<=v; i++)
            for(int j=1; j<=v; j++)
                distance[i][j] = INF;

        Dijkstra(1);
        Dijkstra(v1);
        Dijkstra(v2);

        int min = Math.min(
                distance[1][v1] + distance[v1][v2] + distance[v2][v]
                , distance[1][v2] + distance[v2][v1] + distance[v1][v]);

        if(min >= INF) System.out.println(-1);
        else System.out.println(min);
    }
}