[백준 1504] 특정한 최단 경로

특이사항

• 반드시 거쳐야 하는 정점 2개가 존재

풀이

그래프에 대한 최단경로 값을 구하는 문제이다.
다익스트라 알고리즘을 통해 풀이할 수 있고, 특이사항에 대한 처리를 해주면 된다.

거쳐야 하는 정점

int result1 = 0, result2 = 0;

result1 += dijkstra(1, v1);
result1 += dijkstra(v1, v2);
result1 += dijkstra(v2, N);

result2 += dijkstra(1, v2);
result2 += dijkstra(v2, v1);
result2 += dijkstra(v1, N);

if (result1 >= INF && result2 >= INF) {
    System.out.println(-1);
} else {
    System.out.println(Math.min(result1, result2));
}

• 한번에 다익스트라를 구하는 것이 아니고, 구간을 정해서 구한 후 더해준다.
• INF값을 정의하고, 탐색한 결과값이 INF보다 크다면 해당 구간에 도달하지 못한 것으로 간주한다.

코드

package 특정한최단경로_1504;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<ArrayList<Node>> graph;
    static int[] d;
    static int N;
    static int E;
    static int INF = 200_000_000;

    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());
        E = Integer.parseInt(st.nextToken());
        graph = new ArrayList<>();
        d = new int[N+1];

        for (int i = 0; i <= N; i++) {
            graph.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());
            graph.get(a).add(new Node(b, c));
            graph.get(b).add(new Node(a, c));
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        br.close();

        int result1 = 0, result2 = 0;

        result1 += dijkstra(1, v1);
        result1 += dijkstra(v1, v2);
        result1 += dijkstra(v2, N);

        result2 += dijkstra(1, v2);
        result2 += dijkstra(v2, v1);
        result2 += dijkstra(v1, N);

        if (result1 >= INF && result2 >= INF) {
            System.out.println(-1);
        } else {
            System.out.println(Math.min(result1, result2));
        }
    }

    private static int dijkstra(int start, int end) {

        Arrays.fill(d, INF);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        d[start] = 0;

        while (!pq.isEmpty()) {
            Node poll = pq.poll();
            int now = poll.index;
            int dist = poll.cost;

            if (d[now] < dist) continue;

            for (int i = 0; i < graph.get(now).size(); i++) {
                Node node = graph.get(now).get(i);
                int cost = d[now] + node.cost;
                if (cost < d[node.index]) {
                    d[node.index] = cost;
                    pq.offer(new Node(node.index, cost));
                }
            }
        }

        return d[end];
    }

    static class Node implements Comparable<Node> {
        int index;
        int cost;

        public Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
}

Reference

• 문제
• 풀이참고1
• 풀이참고2