[자바] 백준 23807 - 두 단계 최단 경로 3 (java)

 문제 : boj23807

---

 

필요 알고리즘 개념

• 다익스트라, 브루트포스
  
  • 다익스트라로 거리를 구하고, 세 개의 정점은 브루트포스로 고를 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제에서 중요한건 시작점 x, 목표지점인 z, 그리고 P개의 중간정점 중 3개를 지나야 한다는 점이다. 아주 간단하게 생각해보자. x에서 출발해 P개의 중간정점까지의 최단 거리를 모두 안다고 해보자. 그리고 P개의 중간정점에서 중간정점들끼리의 거리를 모두 알고, z 까지의 거리도 안다고 해보자.

 

  그렇다면 'x -> P개의 중간지점 중에 3개 선택 -> z' 중에 최단거리를 구하면 될 것이다. 그리고 P개의 중간지점 중에 3개를 선택하는건 100P3 이므로 970,200 가지 경우만 보면 된다. 러프하게 생각해서 이렇게 구하면 되는데, 왠지 안될 것 같이 생겼는데 시간 제한이 6초라 된다 ㅋㅋ. 즉 이게 풀이다.

 

  대충 전체적인 시간복잡도는 O(101 x 300000 x log100000 + 100P3) 정도(=O(1.5억)) 나올꺼다. 101은 x에서 다익스트라 돌려야하고, P의 모든 지점에서 다익스트라 돌려야하니 101이다. 30만은 간선의 수, 100000은 정점의 수, 100P3은 위에서 말한대로 3개의 중간지점을 고르는 모든 경우의 수이다.

 

로직은 다음과 같다.

1. x에서 모든 지점으로의 최단거리를 구한다. (다익스트라)

2. P개의 중간 지점에서 모든 지점으로의 최단거리를 구한다. (다익스트라)

3. P개의 중간 지점 중 3개를 고른다(브루트포스). 순서대로 a, b, c라고 하면 x -> a -> b -> c -> z 의 거리합 중 최단거리를 구하면 그게 답이다.

 

다익스트라를 가장한 빡구현문제임

---

 

코드 : github

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

import static java.lang.Math.min;

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

class Pos implements Comparable<Pos> {
    int n;
    long dist;
    public Pos(int n, long dist) {
        this.n = n;
        this.dist = dist;
    }

    @Override
    public int compareTo(Pos o) {
        if (this.dist > o.dist) return 1;
        else if (this.dist < o.dist) return -1;
        return 0;
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final StringBuilder sb = new StringBuilder();
    private static final long INF = 300_000L * 1_000_000L + 1;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        List<Edge>[] edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();

        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            edges[u].add(new Edge(v, w));
            edges[v].add(new Edge(u, w));
        }

        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int z = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(br.readLine());
        int[] pList = new int[p];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < p; i++) {
            pList[i] = Integer.parseInt(st.nextToken());
        }

        Map<Integer, Map<Integer, Long>> distances = new HashMap<>();
        distances.put(x, getDistances(n, x, edges, pList, z));

        for (int i = 0; i < p; i++) {
            int y = pList[i];
            distances.put(y, getDistances(n, y, edges, pList, z));
        }
        edges = null;

        System.out.println(answer(x, pList, z, distances));
    }

    private Map<Integer, Long> getDistances(int n, int start, List<Edge>[] edges, int[] target, int z) {
        long[] dist = new long[n+1];
        Map<Integer, Long> result = new HashMap<>();
        Arrays.fill(dist, INF);

        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.add(new Pos(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Pos cur = pq.poll();
            if (cur.dist > dist[cur.n]) continue;
            for (Edge next : edges[cur.n]) {
                long nextDist = cur.dist + next.w;
                if (nextDist < dist[next.to]) {
                    dist[next.to] = nextDist;
                    pq.add(new Pos(next.to, nextDist));
                }
            }
        }
        result.put(z, dist[z]);
        for (int num : target) {
            result.put(num, dist[num]);
        }
        return result;
    }

    private long answer(int x, int[] pList, int z, Map<Integer, Map<Integer, Long>> distances) {
        int p = pList.length;
        long answer = INF;
        for (int a = 0; a < p; a++) {
            for (int b = 0; b < p; b++) {
                for (int c = 0; c < p; c++) {

                    if (a==b || b==c || a==c) continue;
                    int an = pList[a];
                    int bn = pList[b];
                    int cn = pList[c];
                    answer = min(answer, getTotalDistance(distances, x, an, bn, cn, z));

                }
            }
        }

        return answer >= INF ? -1 : answer;
    }

    private long getTotalDistance(Map<Integer, Map<Integer, Long>> distances, int x, int a, int b, int c, int z) {
        return distances.get(x).get(a) + distances.get(a).get(b) + distances.get(b).get(c) + distances.get(c).get(z);
    }
}