[백준] 1504번 - 특정한 최단 경로 (Gold 4)

문제 링크

백준 1504번 - 특정한 최단 경로 (Gold 4)

문제 설명

가중치가 주어진 그래프에서 시작점, 도착점이 주어져 있다.
반드시 지나가야 하는 두 정점 V1, V2도 주어져 있다.
이 때, 시작점에서 도착점으로 가는 경로 중 V1, V2를 지나가는 최단거리를 출력한다.
불가능하다면 -1을 출력한다.

정답 코드 및 설명

다익스트라 알고리즘은 백준 1753번 - 최단경로 (Gold 4)에서 설명했다.
시작점 I, 반드시 지나가야 하는 두 정점 V1, V2, 도착점 F가 있을 때 가능한 경로는 아래의 두 가지이다.

1. I - V1 - V2 - F
   • V1 - I, V1 - V2, V2 - F의 최단 거리를 다익스트라 알고리즘으로 구해서 더한다.
   • I - V1과 V1 - I의 거리는 같다. 주어진 그래프가 방향성이 없기 때문이다.
2. I - V2 - V1 - F
   • V2 - I, V2 - V1, V1 - F의 최단 거리를 다익스트라 알고리즘으로 구해서 더한다.

두 경로 중 짧은 경로의 길이가 답이 된다.
둘 모두 불가능하다면, -1을 출력한다.

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

public class BOJ1504 {
    
    class Node implements Comparable<Node>{
        int node, minDist;
        Node(int node, int minDist) {
            this.node = node;
            this.minDist = minDist;
        }
        public int compareTo(Node n) {
            return this.minDist - n.minDist;
        }
    }
    
    final int INF = Integer.MAX_VALUE;
    int n, e, v1, v2;
    int[][] adj;
    
    private void input() 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());
        adj = new int[n][n];
        for(int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            adj[a][b] = adj[b][a] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        v1 = Integer.parseInt(st.nextToken()) - 1;
        v2 = Integer.parseInt(st.nextToken()) - 1;
    }
    
    // 다익스트라 알고리즘
    private int[] Dijkstra(int start) {
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;
        while(!pq.isEmpty()) {
            Node curr = pq.poll();
            int currNode = curr.node;
            int currDist = curr.minDist;
            if(dist[currNode] < currDist)
                continue;
            for(int i = 0; i < n; i++) {
                if(adj[currNode][i] == 0)
                    continue;
                if(dist[i] > currDist + adj[currNode][i]) {
                    dist[i] = currDist + adj[currNode][i];
                    pq.add(new Node(i, dist[i]));
                }
            }
        }
        return dist;
    }
    
    private void solution() throws IOException {
        input();
        int dist = INF;
        int[] dist1 = Dijkstra(v1), dist2 = Dijkstra(v2);
        // 1 -> v1 -> v2 -> n
        if(dist1[0] != INF && dist1[v2] != INF && dist2[n-1] != INF)
            dist = dist1[0] + dist1[v2] + dist2[n-1];
        // 1 -> v2 -> v1 -> n
        if(dist2[0] != INF && dist2[v1] != INF && dist1[n-1] != INF)
            if(dist > dist2[0] + dist2[v1] + dist1[n-1])
                dist = dist2[0] + dist2[v1] + dist1[n-1];
        if(dist == INF) dist = -1;
        print(dist);
    }
    
    private void print(int ans) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(ans+"");
        bw.close();
    }
    
    public static void main(String[] args) throws IOException {
        new BOJ1504().solution();
    }

}