[BOJ] 1504 특정한 최단 경로 - Java

✨ 다익스트라 ➔ 최단경로 

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

1504번: 특정한 최단 경로

---

 

 📍 고려해야할 점

• 방향이 없는 그래프이다.
• 1번 정점에서 N번 정점으로 최단거리로 이동한다. 
• 주어진 두 정점을 반드시 거쳐야 한다.
• 두 정점이 v1, v2라면 1 ➔ v1 ➔ v2 ➔ N 또는 1 ➔ v2 ➔ v1 ➔ N 두가지 방법으로 이동할 수 있다.

 

🕹️ 풀이 방법

1️⃣ 노드에 대한 정보 (이동해야하는 노드 = v, 해당하는 노드까지 도달하는데 소요되는 거리 = w)를 입력받는다.

2️⃣ 1 ➔ v1 ➔ v2 ➔ N 으로 가는 방법과 1 ➔ v2 ➔ v1 ➔ N 으로 가는 방법을 다익스트라 알고리즘을 사용하여 구한다.

3️⃣ 시작하는 노드와 목적지 노드를 매개변수로 받아서 다익스트라 알고리즘을 수행한다. 

4️⃣ 두 가지 방법 중 최단거리를 선택해서 출력한다.

 

 

 

👩‍💻 전체 코드

public class BOJ_1504_특정한최단경로 {

    static int N, E;
    static int v1, v2;
    static boolean[] visit;
    static int INF = Integer.MAX_VALUE;
    static int[] dist;

    static ArrayList<Info>[] arrayList;

    static class Info implements Comparable<Info>{
        int v, w;

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

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

    static int dijkstra(int start, int end){
        PriorityQueue<Info> pq = new PriorityQueue<>();
        Arrays.fill(dist, INF);
        visit = new boolean[N + 1];
        pq.add(new Info(start, 0));
        dist[start]=0;

        while (!pq.isEmpty()) {
            Info now = pq.poll();

            if(!visit[now.v]) visit[now.v] = true;

            for (int i = 0; i < arrayList[now.v].size(); i++) {
                Info next = arrayList[now.v].get(i);

                if (!visit[next.v] && dist[next.v] > now.w + next.w) {
                    dist[next.v] = now.w + next.w;
                    pq.add(new Info(next.v, dist[next.v]));
                }
            }
        }
        return dist[end];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        arrayList = new ArrayList[N + 1];
        dist = new int[N + 1];
        visit = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            arrayList[i] = 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());

            arrayList[a].add(new Info(b, c));
            arrayList[b].add(new Info(a, c));
        }

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

        int ans1=0, ans2=0;
        int result;

        // 1 ➔ v1 ➔ v2 ➔ N
        ans1+=dijkstra(1, v1);
        ans1+=dijkstra(v1, v2);
        ans1+=dijkstra(v2, N);

        // 1 ➔ v2 ➔ v1 ➔ N
        ans2+=dijkstra(1, v2);
        ans2+=dijkstra(v2, v1);
        ans2+=dijkstra(v1, N);

        if(ans1>=INF && ans2>=INF) result=-1;
        else result = Math.min(ans1, ans2);

        System.out.println(result);
    }
}