백준 1504 특정한 최단 경로 - JAVA

1504 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.util.*;
import java.io.*;
 
class Node implements Comparable<Node> {
    int target;
    int weight;
    
    Node(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node n) {
        return weight - n.weight;
    }
}
public class Main{
    static int N, E, v1, v2;
    static List<List<Node>> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        } 
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(a).add(new Node(b, c));
            list.get(b).add(new Node(a, c));
        } 
        st = new StringTokenizer(br.readLine());
        v1 = Integer.parseInt(st.nextToken());
        v2 = Integer.parseInt(st.nextToken());
        
        long result1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N);
        long result2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);
        long answer = Math.min(result1, result2);
        
        if (answer >= Integer.MAX_VALUE) {
            bw.write(String.valueOf(-1));
        } else {
            bw.write(String.valueOf(answer));
        }
        bw.flush();
    }
    private static long dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int dist[] = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        pq.offer(new Node(start, 0));
        while(!pq.isEmpty()) {
            Node current = pq.poll();
            if (dist[current.target] >= current.weight) {
                for (Node next : list.get(current.target)) {
                    if (dist[next.target] > current.weight + next.weight) {
                        dist[next.target] = current.weight + next.weight;
                        pq.offer(new Node(next.target, dist[next.target]));
                    }
                } 
            } 
            
        }
        return dist[end];
    }
}

 

알고리즘 설명

---

해당 문제는 v1, v2를 지나는 1부터 N까지의 최단경로 이므로, v1과 v2를 끊어서 생각하시면 편할 것 같습니다. 모든 간선의 가중치는 0을 포함한 양수이기 때문에, 가장 빠른 길은 다음 중 한가지일 수 밖에 없습니다.

1. 1 -> v1 -> v2 ->N
2. 1 -> v2 -> v1 -> N

이렇게 두 가지의 경우의 수를 다익스트라를 활용해 풀어야 하는데, 가장 간단한 방법은 1부터 v1까지 + v1부터 v2까지 + v2부터 N까지의 최단경로를 구해 각각의 최단경로를 더하는 것입니다. 쉽게 생각하긴 어렵지만, 다익스트라 문제는 경험을 통해 데이터를 쌓아가는 것이 가장 빠르게 습득하는 방법인것 같습니다.

 

코드 해석

---

양방향 그래프이므로, 간선 입력 시 a, b, c 값을 각각 list.get(a)에 new Node(b, c)를, list.get(b)에 new Node(a, c)를 추가하여 양쪽 방향의 연결을 모두 저장합니다.

이후, 우선순위 큐에 시작 노드인 new Node(1, 0)을 삽입하고, 현재 노드와 연결된 노드들을 가중치가 낮은 순서부터 탐색합니다.

단, 다음 노드까지의 누적 가중치가 dist 배열에 저장된 값보다 큰 경우, 해당 노드는 우선순위 큐에서 제거만 하고, 탐색을 진행하지 않습니다. 대신 다음 우선순위 큐의 원소를 확인합니다. 이후 result1과 result2의 값을 비교하여 출력합니다. 단 출력할 dist배열의 원소의 값이 int자료형의 최댓값과 크거나 같은 경우 방문하지 못한(연결되지 않은) 노드가 있는 것으로 간주하고 -1을 출력합니다.