[JAVA] BOJ1504 특정한 최단 경로

입력

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

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

 

출력

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

 

풀이

[A->B]->C->D, A->[B->C]->D, A->B->[C->D] 시작점을 바꿔가면서 다익스트라를 돌리는 걸 생각을 못했었다. 구간 별로 다익스트라를 돌린 뒤에 다 더하면 A->B->C->D 를 거쳐가는 최소비용을 구할 수 있다.

그리고 B, C는 순서가 없으므로 A->C->B->D 도 구해야 한다.

위와 같이 동일하게 [A->C]->B->D, A->[C->B]->D, A->C->[B->D] 구간별 최소 가중치를 돌린다.

A->B->C->D, A->C->B->D 둘 중 어느게 더 가중치가 적을지 모르니까 둘다 비교해 본뒤 둘다 INF 라면 -1을, 그게 아니라면 가중치가 적은 쪽을 출력한다.

 

소스코드

import java.util.*;
import java.util.stream.*;
import java.io.*;
import java.math.*;
import java.text.*;

public class Main {

    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    
    
    
    static void solve() throws IOException {
        //System.setIn(new FileInputStream("c:/Dev/git/algo/src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer stt = null;
        stt = new StringTokenizer(br.readLine());
        N = stoi(stt.nextToken());
        M = stoi(stt.nextToken());
        
        // 인접리스트 생성하기
        adj = new ArrayList<>();
        for(int i = 0; i <= N; i++) {
            adj.add(new ArrayList<Node>());
        }
        
        // 엣지 입력 받기
        for(int i = 0; i < M; i++) {
            stt = new StringTokenizer(br.readLine());
            int a = stoi(stt.nextToken());
            int b = stoi(stt.nextToken());
            int c = stoi(stt.nextToken());
            
            adj.get(a).add(new Node(b, c));
            adj.get(b).add(new Node(a, c));
        }
        
        stt = new StringTokenizer(br.readLine());
        int v1 = stoi(stt.nextToken());
        int v2 = stoi(stt.nextToken());
        
        long ans1 = djik(1, v1) + djik(v1, v2) + djik(v2, N); 
        long ans2 = djik(1, v2) + djik(v2, v1) + djik(v1, N); 
        if(ans1 >= Integer.MAX_VALUE && ans2 >= Integer.MAX_VALUE) { print(-1); }
        else { print(Math.min(ans1, ans2)); }
        
        bw.close();
        br.close();
    }
    
    static long djik(int start, int end) {
        boolean[] visited = new boolean[N+1];
        long[] dist = new long[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Node> ascdq = new PriorityQueue<Node>(Comparator.comparing(Node::getCost, Long::compareTo));
        
        //자기 자신을 가는 곳은 거리가 0이니까
        dist[start] = 0;
        ascdq.add(new Node(start, dist[start]));
        
        while(!ascdq.isEmpty()) {
            
             Node nd = ascdq.poll();
             int dest = nd.dest;
             long cost = nd.cost;
             
             // 처음에 미리 방문해 두면 탐색이 끝나서 여기서  세팅해 줘야함
             if(visited[dest]) { continue; }
             visited[dest] = true;
             
             for(Node next : adj.get(dest)) {
                 if(cost + next.cost < dist[next.dest]) {
                     dist[next.dest] = cost + next.cost;
                     ascdq.add(new Node(next.dest/* 다음 장소 */, cost + next.cost/* 다음 장소 갈 비용*/));
                 }
             }
                
        }
        
        return dist[end];        
    }
    
    static List<List<Node>> adj;
    static long[] dist;
    static int N, M; 
    
    public static void main(String[] args) throws IOException {
        solve();
    }
    
    static int stoi(String s) { return Integer.parseInt(s); }
    static long stol(String s) { return Long.parseLong(s); }
    static String itos(int opih) { return Integer.toString(opih); }
    static String itos(Integer opih) { return opih.toString(); }
    static void print(String s) { System.out.println(s); }
    static void print(int opih) { System.out.println(opih); }
    static void print(long opih) { System.out.println(opih); }    
    static void print(char opih) { System.out.println(opih); }    
    static void print(StringBuilder sb) { System.out.println(sb.toString()); }
    static void print() { System.out.println(); }
}

class Node {
    int dest; long cost;
    Node(int dest, long cost) {
        this.dest = dest; this.cost = cost;
    }
    
    public long getDest() { return this.dest; }
    public long getCost() { return this.cost; }
}