백준 22865 자바 - 가장 먼 곳 (BOJ 22865 JAVA)

문제 : boj22865

 

 

  설명이 좀 부족한 부분이 있는 문제이다. 일단 문제 이해부터 해보자. 예제 입력 1을 그래프로 그려보면다음과 같다.

 

 

  위 그래프를 기반으로 어떠한 X 지점에서 시작해서 모든 정점으로 가는 최단거리를 구해보겠다. 이 때, 시작하는 정점인 X는 각각 A,B,C 이다. 예를들어 C인 5번 정점에서 시작할 경우 3번정점까지의 최단거리는 '7'이다. 

 

 

  A,B,C로의 거리를 알아야 하는데 왜 A,B,C에서 시작하는 거리를 잰 것인지 궁금할 수 있다. 이 문제의 경우 무방향 그래프에서 진행되므로, A에서 모든 정점으로 가는 최단거리는 모든 정점에서 A로 가는 최단거리와 동일하다. 

  문제에서 미흡한 부분이, X가 A,B,C가 될 수 있는지 없는지 명확히 제시하지 않았다는 점이다(어차피 시작점들은 거리가 0이라고 보면 문제가 없다고 볼 수도 있으나, 일반적으로 그래프에서 시작점에서 시작점은 무시하고 생각하는 경우가 많아 괜히 오답률을 높히는 꼴이고, 문제 이해 자체도 더디게 한다. 따라서 문제에서 정확히 명시하는게 맞다고 봄). 결론적으로 맞추고 보니, 그냥 A,B,C는 후보군에서 제외하고 풀어도 된다. 따라서 A,B,C에 해당하는 정점들은 제외하고 나머지 정점들만 남겨보자. 그럼 남은 항목들은 A,B,C를 제외한 나머지 정점에서 A,B,C로 가는 최단거리 들이 남게 된다. 

 

  이제 문제에서 원하는 것은 각 정점에서 A,B,C로 가는 최단거리 중 가장 거리가 짧은 것들 중 가장 거리가 긴 곳이다. 따라서 일단 각 정점에서 A,B,C로 가는 가는 최단거리들 중 최단거리만 남긴다.

 

  그럼 정점3에서 A,B,C로 가는 거리 중 가장 짧은 것은 4, 정점 4에서 A,B,C로는 2, 정점 6에서 A,B,C로도 2가 된다. 이 중 가장 거리가 먼 정점 3이 최종 답이 된다. 이제 위의 모든 과정을 구할 수 있는 알고리즘을 적용하면 된다. 이 경우엔 A에서 모든 정점으로의 다익스트라, B에서의 다익스트라, C에서의 다익스트라로 알 수 있다. 따라서 다익스트라 3번으로 풀 수 있다. 최종 시간 복잡도는 대강 O(ElogV + ElogV + ElogV)가 된다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

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

class Node implements Comparable<Node> {
    int n, distFromS;
    public Node(int n, int distFromS) {this.n=n; this.distFromS=distFromS;}

    @Override
    public int compareTo(Node o) {
        return this.distFromS-o.distFromS;
    }
}

public class Main extends FastInput {
    private static final int MAX_DIST = 100000*10000+1;

    private int[] getMinDist(int n, int start, ArrayList<Edge>[] edges) {
        int[] v = new int[n+1];
        Arrays.fill(v, MAX_DIST);

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

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (v[cur.n] < cur.distFromS) continue;
            for (Edge next : edges[cur.n]) {
                int nextDist = cur.distFromS + next.dist;
                if (v[next.to] <= nextDist) continue;
                v[next.to] = nextDist;
                pq.add(new Node(next.to, nextDist));
            }
        }

        return v;
    }

    private void solution() throws Exception {
        int n = nextInt();
        int[] abc = new int[3];
        for (int i = 0; i < 3; i++) abc[i] = nextInt();

        ArrayList<Edge>[] edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();

        int m = nextInt();
        for (int i = 1; i <= m; i++) {
            int d = nextInt();
            int e = nextInt();
            int l = nextInt();
            edges[d].add(new Edge(e, l));
            edges[e].add(new Edge(d, l));
        }

        int[] tmp = new int[n+1];
        Arrays.fill(tmp, MAX_DIST);
        for (int i = 0; i < 3; i++) {
            int[] v = getMinDist(n, abc[i], edges);
            for (int j = 1; j <= n; j++) {
                tmp[j] = Math.min(tmp[j], v[j]);
            }
        }
        for (int i = 0; i < 3; i++) tmp[abc[i]] = MAX_DIST;

        int max = 0;
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (tmp[i] == MAX_DIST) continue;

            if (max < tmp[i]) {
                answer = i;
                max = tmp[i];
            }
        }
        System.out.println(answer);
    }

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

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}