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

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

📄 링크

특정한 최단 경로

---

💡 문제 분석

1번 정점에서 N번 정점까지 이동할 때, 주어진 두 정점을 반드시 경유해서 이동하는 최단 경로를 구하는 문제입니다.

a와 b를 경유해서 N으로 가는 최단 거리를 구하기 위해서는 1 → a → b → n으로 가는 경로와 1 → b → a → a로 가는 경로를 비교해서 최소값을 구해야합니다.

1번 정점과 A, B에서 각각 다익스트라 알고리즘을 사용하여 다른 점으로 가는 최단 거리를 구하여 계산하였습니다.

최단 거리를 구했을 때 아주 큰 값이 나온다면 경로가 존재하지 않는다고 판단하여 -1을 출력하였습니다.

---

⌨️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class _1504_특정한최단경로 {

    static class Edge implements Comparable<Edge> {
        int to, w;

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

        @Override
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }
    static int N, E, a, b;
    static ArrayList<Edge>[] adj;

    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());
        adj = new ArrayList[N + 1];
        for(int i = 0; i < N + 1; i++)
            adj[i] = new ArrayList<>();

        for(int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            adj[from].add(new Edge(to, w));
            adj[to].add(new Edge(from, w));
        }
        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        // 로직 처리
        int[] start = dijkstra(1);
        int[] A = dijkstra(a);
        int[] B = dijkstra(b);

        int ret = Math.min(start[a] + A[b] + B[N], start[b] + B[a] + A[N]);
        System.out.println(ret >= 1000000 ? -1 : ret);
    }

    public static int[] dijkstra(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] dist = new int[N + 1];
        Arrays.fill(dist, 1000000);
        dist[start] = 0;
        pq.add(new Edge(start, 0));

        while(!pq.isEmpty()) {
            Edge cur = pq.poll();
            if(cur.w > dist[cur.to]) continue;
            for(int i = 0; i < adj[cur.to].size(); i++) {
                int next = adj[cur.to].get(i).to;
                int nextDistance = adj[cur.to].get(i).w + cur.w;
                if(nextDistance < dist[next]) {
                    dist[next] = nextDistance;
                    pq.add(new Edge(next, nextDistance));
                }
            }
        }
        return dist;
    }
}

---

📋 회고

• 다익스트라.