[백준 / 골드4] 1504 특정한 최단 경로 (Java)

문제 보기

사용한 것

• 특정 정점에서 시작하여 다른 정점까지의 최단 경로를 구하기 위한 다익스트라
• 다익스트라 구현을 위한 PriorityQueue

풀이 방법

• Edge를 v : 도착 정점, w : 간선 가중치로 만들고 Comparable을 간선 가중치 오름차순으로 구현
• 시작 정점, 도착 정점을 인자로 받아 두 정점간 최단 경로를 구하는 dijkstra() 구현
• 1 ~ n 의 경로 중 v1, v2를 거치는 최단 경로를 구함, 다음 중 최소 값이 정답
  • 모든 경로는 최단 경로
  • 1 ~ v1 + v1 ~ v2 + v2 ~ n
  • 1 ~ v2 + v2 ~ v1 + v1 ~ n

코드

public class Main {

    public static int n;
    public static List<List<Edge>> map;

    public static void main(String[] args) throws IOException {
        map = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        int e = Integer.parseInt(line[1]);
        for (int i = 0; i <= n; i++) {
            map.add(new ArrayList<>());
        }
        for (int i = 0; i < e; i++) {
            line = br.readLine().split(" ");
            int v1 = Integer.parseInt(line[0]);
            int v2 = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            map.get(v1).add(new Edge(v2, w));
            map.get(v2).add(new Edge(v1, w));
        }
        line = br.readLine().split(" ");
        int v1 = Integer.parseInt(line[0]);
        int v2 = Integer.parseInt(line[1]);

        int v1ToV2 = dijkstra(v1, v2);
        int oneToV1 = dijkstra(1, v1);
        int v2ToN = dijkstra(v2, n);
        int oneToV2 = dijkstra(1, v2);
        int v1ToN = dijkstra(v1, n);

        System.out.println(getAnswer(v1ToV2, oneToV1, v2ToN, oneToV2, v1ToN));
    }

    public static int dijkstra(int start, int end) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();

            if (dist[edge.v] < edge.w) {
                continue;
            }

            for (Edge nextEdge : map.get(edge.v)) {
                int w = dist[edge.v] + nextEdge.w;

                if (w < dist[nextEdge.v]) {
                    dist[nextEdge.v] = w;
                    pq.offer(new Edge(nextEdge.v, w));
                }
            }
        }

        return dist[end];
    }

    public static int getAnswer(int v1ToV2, int oneToV1, int v2ToN, int oneToV2, int v1ToN) {
        if (v1ToV2 == Integer.MAX_VALUE) {
            return -1;
        }

        int dist1;
        if (oneToV1 == Integer.MAX_VALUE || v2ToN == Integer.MAX_VALUE) {
            dist1 = Integer.MAX_VALUE;
        } else {
            dist1 = oneToV1 + v1ToV2 + v2ToN;
        }

        int dist2;
        if (oneToV2 == Integer.MAX_VALUE || v2ToN == Integer.MAX_VALUE) {
            dist2 = Integer.MAX_VALUE;
        } else {
            dist2 = oneToV2 + v1ToV2 + v1ToN;
        }

        return dist1 == Integer.MAX_VALUE && dist2 == Integer.MAX_VALUE ? -1
            : Math.min(dist1, dist2);
    }
}

class Edge implements Comparable<Edge> {

    public int v;
    public int w;

    public Edge(int v, int w) {
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Edge o) {
        return w - o.w;
    }
}