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

이 문제는 다익스트라 알고리즘을 이용하여 중간에 정점 v1과 v2를 거쳐 N으로 갈 때의 최단 경로의 길이를 구하는
문제입니다.

이 문제를 풀기 위해서는 우선 정점 1에서 v1과 v2로 갈 때의 최단 경로의 길이를 구해야 합니다.

만약 경로가 존재하지 않을 경우에는 그다음 단계를 진행하지 않아도 됩니다.

1에서 v1으로 가는 경로가 없다고 가정하면 1에서 v2로 가는 최단 경로를 구하고 그 후 v2에서 v1으로 가는 최단 경로를 구해야 합니다.

v2와 v1을 모두 거쳐야 하기 때문에 이 경로를 구해줍니다.

그리고 마지막으로 v1에서 N으로 가는 최단 경로를 구한 후 이 3개의 경로의 길이를 더한 값을 출력합니다.

이에 대해서 예제 1번을 예시로 설명드리겠습니다.

위 그림은 예제 1번을 나타낸 그림입니다.

이 예제에서는 1번에서 시작하여 2와 3을 거쳐서 4로 가는 최단 경로를 찾습니다.

따라서 우선 1에서 2로 가는 최단 경로를 찾습니다.

1에서 2로 가는 최단 경로는 이와 같습니다.

그리고 2에서 3으로 가는 최단 경로는 아래의 그림과 같습니다.

마지막으로 3에서 4로 가는 최단 경로는 아래와 같습니다.

이 3가지의 경로를 다 합치면 아래의 그림과 같습니다.

이 경로의 길이를 합치면 7이 됩니다.

이제 1에서 3으로 먼저 갈 때를 확인해보겠습니다.

1에서 3으로 갈 때의 최단 경로는 다음과 같습니다.

그리고 3에서 2로 갈 때의 최단 경로는 다음과 같습니다.

2에서 4로 갈 때의 최단 경로는 다음과 같습니다.

이 경로를 모두 합치면 다음과 같습니다. 주황색 선은 이 경로를 2번 이용했다는 의미입니다.

5 + 3 + 4 = 12 따라서 이 경로의 길이는 12입니다.

2를 먼저 거쳤을 때의 길이가 7로 더 빠르므로 이 경로를 선택해 줍니다.

위에서 설명드렸을 때 각각의 경로로 찾아갈 때 다익스트라 알고리즘을 이용하여 최단 경로를 찾았습니다.

이제 코드를 보여드리겠습니다.

---

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

public class Main {
    static List<List<Node>> l = new ArrayList<>();
    static int N, E;

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

        for(int i = 0; i<=N; i++)
            l.add(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 cost = Integer.parseInt(st.nextToken());

            l.get(A).add(new Node(B, cost));
            l.get(B).add(new Node(A, cost));
        }

        //v1, v2를 입력 받아 두 정점을 거쳐 N으로 갈 때의 최단 경로의 거리 계산
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        int toV1 = dijkstra(1, v1);
        int toV2 = dijkstra(1, v2);

        int v1Tov2 = dijkstra(v1, v2);

        int v2ToN = dijkstra(v2, N);
        int v1ToN = dijkstra(v1, N);

        boolean flagV1 = true;
        boolean flagV2 = true;

        if(toV1 == -1 || v1Tov2 == -1 || v2ToN == -1)
            flagV1 = false;
        if(toV2 == -1 || v1Tov2 == -1 || v1ToN == -1)
            flagV2 = false;

        int sumV1 = -1;
        int sumV2 = -1;

        if(flagV1)
            sumV1 = toV1 + v1Tov2 + v2ToN;
        if(flagV2)
            sumV2 = toV2 + v1Tov2 + v1ToN;

        printAnswer(sumV1, sumV2);
    }

    static int dijkstra(int start, int to){
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        //PriorityQueue를 사용해서 chooose 메소드, 즉 시작 정점에 연결된 정점 중
        //가장 가중치가 작은 노드를 찾지 않아도 되도록 해줌
        Queue<Node> q = new PriorityQueue<>();
        boolean[] visited = new boolean[N+1];
        q.offer(new Node(start, 0));

        while(!q.isEmpty()){
            Node a = q.poll();

            if(visited[a.vertex])
                continue;

            visited[a.vertex] = true;
            //a 노드를 경유해서 l.get(a.vertex).get(i)에 있는 노드로 이동
            for(int i = 0; i<l.get(a.vertex).size(); i++){
                Node nextNode = l.get(a.vertex).get(i);

                if(dist[nextNode.vertex] > dist[a.vertex] + nextNode.cost){
                    dist[nextNode.vertex] = dist[a.vertex] + nextNode.cost;
                    q.offer(new Node(nextNode.vertex, dist[nextNode.vertex]));
                }
            }
        }

        if(dist[to] == Integer.MAX_VALUE)
            return -1;
        else
            return dist[to];
    }

    static void printAnswer(int v1, int v2){
        if(v1 == -1 && v2 == -1)
            System.out.println(-1);
        else if(v1 == -1)
            System.out.println(v2);
        else if(v2 == -1)
            System.out.println(v1);
        else
            System.out.println(Math.min(v1, v2));
    }
}
class Node implements Comparable<Node>{
    int vertex, cost;

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

넘어간 정점마다 다익스트라 알고리즘을 이용하여 그다음 정점까지의 최단 경로를 찾아주었습니다.