Baekjoon | Q.1504 - 특정한 최단경로

1504번: 특정한 최단 경로

 다익스트라 알고리즘을 이용하여 최단 경로를 찾는 문제에서 경유지 두 군데가 추가된 문제이다.

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  static class Node implements Comparable<Node>{
    int v;
    int d;

    public Node(int v, int d) {
      this.v = v;
      this.d = d;
    }

    @Override
    public int compareTo(Node target) {
      if(this.d > target.d) {
        return 1;
      }else if(this.d < target.d) {
        return -1;
      }
      return 0;
    }
  }

  static ArrayList<Node>[] g;
  static int N;
  static int E;
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    N = sc.nextInt();
    E = sc.nextInt();

    g = new ArrayList[N+1];

    for (int i = 1; i < g.length; i++) {
      g[i] = new ArrayList<>();
    }

    for (int i = 0; i < E; i++) {
      int n1 = sc.nextInt();
      int n2 = sc.nextInt();
      int d = sc.nextInt();
      
      g[n1].add(new Node(n2, d)); // 그래프 간선 추가
      g[n2].add(new Node(n1, d)); // 그래프 간선 추가 (양방향)
    }
    
    // 반드시 거쳐야 하는 정점
    int v1 = sc.nextInt();
    int v2 = sc.nextInt();
    
    sc.close();

    int total1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N);
    int total2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);
    
    int total = Math.min(total1, total2);
    
    if(total >= Integer.MAX_VALUE || E == 0) System.out.println(-1);
    else System.out.println(total);

  }

  public static int dijkstra(int start, int end) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    int[] dis = new int[N+1];
    
    for (int i = 1; i < dis.length; i++) {
      dis[i] = Integer.MAX_VALUE;
    }

    pq.add(new Node(start, 0));
    dis[start] = 0;

    while(!pq.isEmpty()) {
      Node now = pq.poll();

      for (Node next : g[now.v]) {
        int new_d = dis[now.v] + next.d;
        if(dis[next.v] > new_d) {
          dis[next.v] = new_d;
          pq.add(new Node(next.v, dis[next.v]));
        }
      }
    }

    return dis[end];
  }
}

출발 -> 경유지1 -> 경유지2 -> 도착 / 출발 -> 경유지2 -> 경유지1 -> 도착의 최단 경로를 찾아 두 가지 중 더 짧은 경로를 출력해주었다.

 

 간선이 하나도 없는 테스트 케이스에 자꾸 Integer.MAX_VALUE 보다 작은 값이 출력되어서 따로 if문 처리를 해주었다... 왜인지 아직도 모르겠음 ㅠㅠ