[Boj_1504] 특정한 최단 경로

📎 문제 링크

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

1504번: 특정한 최단 경로

 

▸ 문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

 

▸ 입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

 

▸ 출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 4
• 🔔  문제 유형 : 그래프 이론, 데이크스트라, 최단 경로
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

• 각 노드에 연결된 [정점, 비용]을 저장할 인접리스트와 시작점에서 각 정점으로 가는 최단거리를 저장할 dist 배열을 만들어주었다.
• 방향성이 없는 그래프이므로 양방향 그래프를 인접 리스트로 표현해 주었다.
• dist 배열의 초깃값 INF는 오버플로우가 나지 않도록 최대 간선 개수 * 최대 거리인 200000000으로 설정해 주었다.
• 임의로 주어진 두 정점(u, v)을 반드시 통과해야 하므로 두 가지 경우로 나누어 생각했다.
  • i -> u -> v -> n
  • i -> v -> u -> n
• 1번의 경우, 1에서 u까지 다익스트라 알고리즘 수행, u에서 v까지 다익스트라 알고리즘 수행, v에서 n까지 다익스트라 알고리즘을 수행하여 각각의 최단 거리에 대해 모두 더해준다.
• 2번의 경우도 마찬가지로 각각의 최단거리를 모두 더해준 후, 1번에서 구한 결괏값을 비교하여 더 작은 값으로 출력했다.
• 이때, 1번의 경우와 2번의 경우에서 얻어낸 값이  INF보다 크거나 같다면 u, v를 거쳐 n에 도달할 수 없다는 의미이므로 -1을 출력했다.

 

✔ 최종 코드

메모리 : 68612KB
시간 : 820ms

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int n, e;
    static int u, v;
    static ArrayList<ArrayList<pos>> list;
    static int[] dist;
    static boolean[] checked;
    static PriorityQueue<pos> pq;

    static public class pos implements Comparable<pos> {
        int end;
        int dist;

        public pos(int end, int dist) {
            this.end = end;
            this.dist = dist;
        }

        @Override
        public int compareTo(pos o) {
            return this.dist - o.dist;
        }
    }
    static int INF = 200000000; // 최대 간선 개수 * 최대 거리
    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()); // 간선의 개수

        list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            // a -> b, b -> a
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // 그 거리가 c
            int c = Integer.parseInt(st.nextToken());

            // 양방향
            list.get(a).add(new pos(b, c));
            list.get(b).add(new pos(a, c));
        }

        // 반드시 거쳐야 하는 두 개의 서로 다른 정점
        st = new StringTokenizer(br.readLine());
        u = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        int distA = 0; // u -> v일때 최단거리
        distA += dijkstra(1, u);
        distA += dijkstra(u, v);
        distA += dijkstra(v, n);

        int distB = 0; // v -> u일때 최단거리
        distB += dijkstra(1, v);
        distB += dijkstra(v, u);
        distB += dijkstra(u, n);

        int ans = (distA >= INF && distB >= INF) ? -1 : Math.min(distA, distB);
        bw.append(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static int dijkstra(int start, int end) {
        dist = new int[n+1];
        Arrays.fill(dist, INF);

        pq = new PriorityQueue<>();
        pq.offer(new pos(start, 0));
        checked = new boolean[n+1];
        dist[start] = 0;

        while (!pq.isEmpty()) {
            pos now = pq.poll();
            checked[now.end] = true;

            for (pos next : list.get(now.end)) {
                if (!checked[next.end] && dist[next.end] > dist[now.end] + next.dist) {
                    dist[next.end] = dist[now.end] + next.dist;
                    pq.offer(new pos(next.end, dist[next.end]));
                }
            }
        }
        return dist[end];
    }
}

 

 

📍 함께 풀어보면 좋은 백준 문제

• 최단경로
• 특정 거리의 도시 찾기
• 지름길