백준 20010 - 악덕 영주 혜유

문제

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

리뷰

주어진 문제에서 구해할 것은 다음 두 가지이다.

• MST를 구성하는 간선들의 비용 합
• MST내에서 임의의 두 마을을 잇는 최단 경로 중 가장 비용이 큰 경로의 비용(maxCost)

MST를 구성하는 간선들의 비용 합의 경우 크루스칼을 실행하며 채택되는
간선들의 비용 합을 구해주면 되기 때문에, 그리 어렵지 않았다.

관건은 maxCost를 구하는 것이었다. 생각해보면 MST도 결국 하나의 그래프이다.
따라서 한 정점에서 가장 먼 정점까지 순차적으로 탐색을 진행하는 DFS를 통해
접근하였다.

먼저 크루스칼 로직내에서 채택된 간선을 모아 인접 리스트의 형태로
그래프(graph)를 구성하였다. DFS에서 이 그래프를 이용하여 각 정점을 출발점으로 하여 탐색을 진행하며 dfs의 두번째 파라미터인 cost에 탐색시 비용을 누적하고
이를 maxCost와 비교하여 갱신하며 가장 큰 비용을 도출할 수 있게 설계하였다.

로직의 시간복잡도는 크루스칼이 $O(NlogK)$, 각 정점별로 DFS를 실행하는 부분이
$O(N(N+N-1)) = O(N^2)$ 형태를 띄므로 더 큰 $O(N^2)$으로 수렴하고 이는
$N=1,000$인 최악의 경우에도 제한 조건 0.5초를 무난히 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int N;
    static int[] parent;
    static boolean[] visited;
    static long maxCost = MIN_VALUE;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));
    static List<List<Node>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        parent = new int[N];
        visited = new boolean[N];

        for (int i = 0; i < N; i++)
            graph.add(new ArrayList<>());

        int u, v, w;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = parseInt(st.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        long sum = kruskal();

        for (int i = 0; i < N; i++) {
            Arrays.fill(visited, false);
            dfs(i, 0);
        }

        System.out.println(sum);
        System.out.println(maxCost);
        br.close();
    }

    static void dfs(int cur, int cost) {
        visited[cur] = true;
        maxCost = Math.max(maxCost, cost);

        for (Node next : graph.get(cur)) {
            if (visited[next.u]) continue;

            dfs(next.u, cost + next.w);
        }
    }


    static long kruskal() {
        Arrays.fill(parent, -1);

        int selected = 0;
        long sum = 0;

        while (!pq.isEmpty() && selected < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) continue;

            selected++;
            sum += e.w;
            graph.get(e.u).add(new Node(e.v, e.w));
            graph.get(e.v).add(new Node(e.u, e.w));
        }

        return sum;
    }


    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return false;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }

        return true;
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static class Node {
        int u, w;

        public Node(int u, int w) {
            this.u = u;
            this.w = w;
        }
    }

    static class Edge {
        int u, v, w;

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

결과