[BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름)

 

 

---

문제 링크 

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

20010번: 악덕 영주 혜유

 

문제 풀이

최소 가중치를 가지는 MST는 구했는데, 두번째 값을 구하지 못해 3시간을 소비했다. 찾아본 결과 트리의 지름을 구하는 방법을 몰랐고, 문제 지문을 제대로 읽지 못해 MST 트리 정보를 활용하는 것을 파악하지 못했다..(반성)

 

 

문제 지문을 다시 보면 아래와 같다

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

 

절차

1) Kruskal (크루스칼) 알고리즘을 사용하여 최소 간선 비용과 MST를 구성하는 간선 정보를 구한다

- Prime 사용할 경우 힙에서 최소 가중치를 가지는 노드를 꺼낼 때 이전 노드에 대한 정보도 필요

 

2) DFS 2번 실행하여 MST 트리 지름 구함- MST를 구성하는 인접 리스트 정보를 1)에서 저장한 뒤 트리의 지름 구한다

2-1) MST 트리에서 임의 노드 선택하여 dfs 통해 최대 가중치를 가지는 leaf 노드를 구한다  (leaf = 지름을 구성하는 한 점)

2-2) 2-1)에서 구한 leaf 노드로 dfs 한번 더 실행하여 구한 최대값이 트리의 지름이 된다 

마을을 이동하는 최단 경로(MST) 중 비용이 가장 큰 경로의 비용 == MST의 지름

 

시간복잡도 

1) 크루스칼 알고리즘 : O(ElogE)

2) 트리의 지름을 구하는 dfs 2번 수행 : O(N^2)

 

 

참고. 트리의 지름 

https://www.youtube.com/watch?v=gIROKVJV6w8 

 

참고. 백준 1167번 트리의 지름

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

1167번: 트리의 지름

 

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
  static StringBuilder sb = new StringBuilder();

    static int N, K;
    static int leaf, max;
    static List<Edge>[] adj;

    static int[] parent;
    static List<Node> nodeList;

    static boolean[] visit;

    static class Node implements Comparable<Node> {
        int x;
        int y;
        int cost;

        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        // 오름차순 정렬
        @Override
        public int compareTo(Node node) {
            return cost - node.cost;
        }
    }

    static class Edge implements Comparable<Edge> { // MST로 최소 연결된 간선 정보 저장
        int idx;
        int cost;

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

        public int getIdx() {
            return idx;
        }

        public int getCost() {
            return cost;
        }

        @Override
        public int compareTo(Edge edge) {
            return cost - edge.cost;
        }
    }

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 마을 수 (노드)
        K = Integer.parseInt(st.nextToken()); // 설치 가능한 교역로의 수 (간선)

        nodeList = new ArrayList<>();
        adj = new ArrayList[N];
        for(int i = 0; i < N; i++) {
            adj[i] = new ArrayList<>();
        }

        for(int i = 1; i <= K; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            nodeList.add(new Node(from, to, cost));
        }

        visit = new boolean[N];
    }

    static int getParent(int node) {
        if(parent[node] == node) return node;

        return parent[node] = getParent(parent[node]);
    }

    static void union(int a, int b) {
        int _a = getParent(a);
        int _b = getParent(b);

        if(_a < _b) parent[_b] = _a;
        else parent[_a] = _b;
    }

    static boolean unionFind(int a, int b) {
        int _a = getParent(a);
        int _b = getParent(b);

        return _a == _b;
    }

    // 최소 신장 트리, 최소 가중치
    static int kruskal() {
        Collections.sort(nodeList);

        parent = new int[N];
        for(int i = 0; i < N; i++) parent[i] = i;

    
        int result = 0;
        for(Node node : nodeList) {
            if(!unionFind(node.x, node.y)) {
                result += node.cost;
                union(node.x, node.y);
                
                // MST 구성하는 간선 정보를 인접리스트에 양방향으로 담는다
                adj[node.x].add(new Edge(node.y, node.cost));
                adj[node.y].add(new Edge(node.x, node.cost));
            }
        }

        return result;
    }

    static void dfs(int node, int dist) {
        visit[node] = true;

        if(max < dist) {
            leaf = node;
            max = dist;
        }

        for(Edge next : adj[node]) { //adj : MST 구성하는 인접 리스트 정보
            if(!visit[next.idx]) {
                dfs(next.idx, dist + next.cost);
            }
        }
    }

    static void pro() {
        // 1. 최소 가중치, MST 트리 정보 구함
        int min = kruskal();
        sb.append(min).append("\n");
        
        // 2. MST 트리의 지름 구하기
        Arrays.fill(visit, false);
        max = Integer.MIN_VALUE;
        dfs(0, 0);

        Arrays.fill(visit, false);
        max = Integer.MIN_VALUE;
        dfs(leaf, 0);

        sb.append(max).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();

        pro();

        System.out.println(sb.toString());
    }
    
}