자바(백준) 1504 특정한 최단 경로

오답 노트 & 새로 알게 된 점

다익스트라의 기본 문제이다.

1번 정점에서 시작하여 특정한 두 정점을 지나서 N에 도착할 때의 길이를 구하는 것이다.

모든 정점을 갈 때마다 최단 경로로 이동해야한다.

그래서 1번 정점, 특정한 두 정점을 각각 시작점으로 하는 다익스트라를 사용했다.

dist를 2차원 배열로 만들어 dist[N][0]에는 1번 정점의 각 노드마다 경로, dist[N][1], dist[N][2]에는 특정한 두 정점의 최단 경로 데이터를 넣었다.

 

그리고 실수할 수 있는 부분은 하나라도 연결되있지 않으면 즉, 필요하는 dist의 값이 INF값이면 -1을 출력해야한다.

 

---

 

코드

package Graph;
 
import java.io.*;
import java.util.*;
 
public class BOJ1504 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int dist[][];
    static ArrayList<Node> node[];
    static int nV, nE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        nV = atoi(st.nextToken());
        nE = atoi(st.nextToken());
 
        dist = new int[nV + 1][3];
        node = new ArrayList[nV + 1];
 
        for (int i = 0; i <= nV; i++) {
            node[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < nE; i++) {
            st = new StringTokenizer(br.readLine());
            int from = atoi(st.nextToken());
            int to = atoi(st.nextToken());
            int wei = atoi(st.nextToken());
 
            node[from].add(new Node(to, wei));
            node[to].add(new Node(from, wei));
        }
 
        st = new StringTokenizer(br.readLine());
 
        int first = atoi(st.nextToken()); //지나야하는 노드1
        int sec = atoi(st.nextToken()); //지나야하는 노드2
 
        dijkstra(1, 0); //정점 1에서 시작하는 다익스트라 정보
        dijkstra(first,1); //지나야하는 노드1에서 시작하는 다익스트라 정보
        dijkstra(sec, 2); //지나야하는 노드2에서 시작하는 다익스트라 정보
 
        int sum1 = -1, sum2 = -1;
        if (dist[first][0] != Integer.MAX_VALUE && dist[sec][1] != Integer.MAX_VALUE &&
                dist[nV][2] != Integer.MAX_VALUE) {
            sum1 = dist[first][0] + dist[sec][1] + dist[nV][2];
        }
 
        if (dist[sec][0] != Integer.MAX_VALUE && dist[first][2] != Integer.MAX_VALUE &&
                dist[nV][1] != Integer.MAX_VALUE) {
            sum2 = dist[sec][0] + dist[first][2] + dist[nV][1];
        }
 
        int rel = Math.min(sum1, sum2);
 
        System.out.println(rel);
    }
 
    static void dijkstra(int start, int order) {
 
        for (int i = 1; i <= nV; i++) {
            dist[i][order] = Integer.MAX_VALUE;
        }
 
        PriorityQueue<Info> pq = new PriorityQueue<>((o1,o2)->{
            return o1.dist - o2.dist;
        });
 
        pq.offer(new Info(start, 0));
        dist[start][order] = 0;
 
        while (!pq.isEmpty()) {
            Info info = pq.poll();
 
            if(info.dist != dist[info.idx][order]) continue;
 
            for (Node n : node[info.idx]) {
 
                if(dist[info.idx][order] + n.wei >= dist[n.to][order]) continue;
 
                dist[n.to][order] = dist[info.idx][order] + n.wei;
                pq.add(new Info(n.to, dist[n.to][order]));
            }
        }
 
    }
    static class Node{
        int to, wei;
 
        public Node(int to, int wei) {
            this.to = to;
            this.wei = wei;
        }
    }
    static class Info{
        int idx, dist;
 
        public Info(int idx, int dist) {
            this.idx = idx;
            this.dist = dist;
        }
    }
}