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

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

풀이

전형적인 다익스트라 알고리즘 문제.

최단경로 응용 문제로 진행 과정을 자세하게 적어뒀다. 

 

다익스트라에 대해서 처음 접하시는 분은 아래 링크를 먼저 읽어보는 걸 추천한다.

https://sookr5416.tistory.com/160

자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리

다익스트라 알고리즘은 한 노드에서 모든 노드 사이의 최단거리를 구할 수 있는 알고리즘이다.

 

위 문제에서는 특정 노드 2개를 반드시 방문해야된다고 적혀있다.

복잡하게 생각할 것 없다. 다익스트라의 알고리즘을 쪼개서 경로를 찾아주면 된다.

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N;
    static ArrayList<Node>[] arrList;
    public static class Node implements Comparable<Node> {
        int e;
        int v;
		
        public Node (int e, int v) {
            this.e = e;
            this.v = v;
        }
		
        public int compareTo (Node o) {
            return this.v - o.v;
        }
    }
	
    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());
        int E = Integer.parseInt(st.nextToken());
		
        arrList = new ArrayList[N+1];
        for (int i=1; i<=N; i++) {
            arrList[i] = new ArrayList<Node>();
        }
		
        for (int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
			
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
			
            arrList[start].add(new Node(end, value));
            arrList[end].add(new Node(start, value));
        }
		
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
		
        // 1번
        long first = 0;
        first += Dijkstra(1, v1);
        first += Dijkstra(v1, v2);
        first += Dijkstra(v2, N);
		
        // 2번
        long second = 0;
        second += Dijkstra(1, v2);
        second += Dijkstra(v2, v1);
        second += Dijkstra(v1, N);
		
        if (Math.min(first, second) >= 200000000) System.out.println(-1);
        else System.out.println(Math.min(first, second));
    }
	
    public static int Dijkstra(int start, int end) {
        int[] dp = new int[N+1];
        Arrays.fill(dp, 200000000); // 200,000(E의 최대값) * 1,000(c의 최대값) - overflow 방지
		
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dp[start] = 0;
		
        while (!pq.isEmpty()) {
            Node now = pq.poll();
			
            for (Node n : arrList[now.e]) {
                if (dp[n.e] > dp[now.e] + n.v) {
                    dp[n.e]= dp[now.e] + n.v;
                    pq.add(new Node(n.e, dp[n.e]));
                }
            }
        }
		
        return dp[end];
    }
}