[ BOJ ][JAVA][20010] 악덕 영주 혜유

www.acmicpc.net/problem/20010

20010번: 악덕 영주 혜유

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초	512 MB	159	94	73	57.480%

문제

FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, 교역로는 양 방향으로 이동할 수 있으며, 서로 도달이 불가능한 마을이 없도록 교역로를 건설하여야 한다.

마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 모든 마을과 마을을 최소한의 비용으로 연결하고 그 비용을 구해보자. 또한 혜유는 이때 마을과 마을을 이동하는 가장 최악의 비용이 얼마인지에 관심이 많다. 임의의 두 마을을 이동하는 최단 경로 중 비용이 가장 큰 경로의 비용도 구해보자.

입력

첫 번째 줄에는 마을의 수 N(1 ≤ N ≤ 1,000)과 설치 가능한 교역로의 수 K(1 ≤ K ≤ 1,000,000)가 주어진다.

두 번째 줄부터 K + 1줄에는 서로 다른 두 마을의 번호 a, b (a ≠ b)와 두 마을을 연결하는 비용 c가 주어진다. (1 ≤ c ≤ 1,000,000)

항상 모든 마을을 연결할 수 있는 경우만 입력으로 주어진다, 또한 최소 비용으로 연결하는 방법은 유일하다.

서로 다른 두 마을 사이에 건설할 수 있는 교역로는 최대 하나뿐이다.

마을은 0부터 N - 1 사이의 번호를 갖는다.

출력

첫 번째 줄에는 모든 마을을 연결하는 최소 비용을 출력한다.

두 번째 줄에는 마을과 마을을 이동하는 비용이 가장 큰 경로의 비용을 출력한다.

예제 입력 1

6 7
0 1 5395
0 2 540
0 4 7096
1 2 1051
2 4 4750
3 4 9616
3 5 9476

예제 출력 1

25433
24893

예제 입력 2

7 9
0 1 4068
0 3 9921
1 4 474
2 3 421
2 5 9685
3 4 1182
3 5 1690
4 6 9761
5 6 644

예제 출력 2

8479
8058

코드

/*
    악덕 영주 혜유
    최소 스패닝 트리 : MST -> Union-Find (Union-by-rank)
    트리의 지름 : dfs 2번 돌리기
*/
import java.io.*;
import java.util.*;

public class p20010 {
    static class Edge implements Comparable<Edge> {
        int u, v, cost;
        public Edge (int u, int v, int cost) {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }

        public Edge (int v, int cost) {
            this.v = v;
            this.cost = cost;
        }

        public int compareTo(Edge o) {
            return cost - o.cost;
        }
    }
    static final int INF = 987654321;
    static List<Edge>[] list;
    static int n, k, leaf;
    static long answer = 0;
    static int[] parent, rank;
    static PriorityQueue<Edge> pq;
    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());
        k = Integer.parseInt(st.nextToken());

        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        rank = new int[n];
        list = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        pq = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            pq.add(new Edge(u, v, cost));
        }

        mst();

        leaf = 0;
        // 가장 먼 노드(leaf)를 구한다.
        dfs(0, 0, new boolean[n]);
        // 가장 먼 노드에서 다시 dfs를 돈다.
        dfs(leaf, 0, new boolean[n]);
        System.out.println(answer);
    }

    static void mst() {
        int ret = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            int u = cur.u;
            int v = cur.v;
            int cost = cur.cost;
            if (find(u) == find(v)) continue;

            union(u, v);
            ret += cost;
            // union-find를 통해 최소 스패닝 트리를 구성하면서 해당 간선들을 graph에 추가한다.
            // !! union이 진행 된 후 알짜배기 간선들로만 graph를 만들어야 한다.
            list[u].add(new Edge(v, cost));
            list[v].add(new Edge(u, cost));
        }
        System.out.println(ret);
    }

    static void dfs(int now, int sum, boolean[] visited) {
        visited[now] = true;
        if (answer < sum) {
            answer = sum;
            leaf = now;
        }
        for (Edge edge : list[now]) {
            if (visited[edge.v]) continue;
            dfs(edge.v, sum + edge.cost, visited);
        }
    }

    static void union(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            if (rank[u] < rank[v]) {
                parent[u] = v;

            } else {
                parent[v] = u;

                if (rank[u] == rank[v]) {
                    rank[u]++;
                }
            }
        }
    }

    static int find(int x) {
        if (x == parent[x]) return x;

        return find(parent[x]);
    }

}